Computer Networks

• Principles of Network Applications

  • Application Architecture

    While network architecture describes how a bunch of computers are connected, an application architecture describes what roles the computers perform for an application distributed over the computers in a network

  • 2 types of app. arch.

    • Client-server

      Here, there are a bunch of servers that the clients communicate with. Thus, the clients communicate with each other indirectly, through the server.

      The servers have a fixed IP address.

    • P2P

      In person-to-person architecture, there is no reliance on a server.

      The computers (peers) interact with each other directly.

    • Hybrid architecture

      Some application do part of the process in a P2P manner and other parts using servers.

      For example, a typical messaging application establishes connection with fixed servers to get the IP addresses of the users. So, when a user want to connect to another user, it can fetch the IP address of that user from the server, and then request a P2P connection.

      P2P architecture is self-scalable, since there’s very minimal server usage.

      Of course, this decentralisation comes with increases security threats.

  • Process based communication

    The communication in application layer happens when a process $P_A$ running of end system $A$ sends messages over the network to be read by process $P_B$ running on end system $B$ .

    Of course, this repeats like a table tennis match, with many round trips.

    The process that started all this by requesting a connection is called the “client” process, and the other one is called the “server” process. This terminology is independent of app. arch. . Even in P2P , there are client and server processes.

  • Socket

    The communication between processes $P_A,P_B$ happens through a software interface called a “socket” .

    The socket is the “application programming interface” (API) for the application developers.

    

  • Port

    Since the communication is actually between $P_A,P_B$ , and not just $A,B$ , so the sending process $P_A$ must also specify the “port” on which $P_B$ is running on $B$ .

    You must have seen port numbers being used. Say, for docker containers, or for connecting to a database, or some LLM API, or while using a file transfer application, or SSH, or anything related to the internet.

    There are some unsaid rules for deciding the port. Conventionally,

    • A web server is ran on port 80

    • A mail server (using SMTP) on port 25

    • A development server runs on port 8000

  • Transport layer services available

    Since there can be many transport layer protocols to choose from for a socket, we need to consider the services that can be provided by different protocols

    • Reliable Data Transfer

      The application layer won’t have to worry about packet loss or failed message transfer.

      This may not be needed in loss-tolerant applications, like voice call, where packet loss is fine.

    • Throughput

      There are 2 kinds of applications :

      • Bandwidth-sensetive : throughput must not be below a threshold value throughout the session. Eaxmple : voice call

      • Elastic : Throughput can vary, and can even drop to 0 at some points, and the application will still be fine. Example : File transfer

      Here, by “throughput” we mean the instantaneous throughput.

    • Timing

      Guarantees for the end-to-end delay for the packets.

      This is useful for things like Multi-player games, where the time between a key-press and the action being done by a character on the screen should be minimal.

    • Security

      • Confidentiality (encryption)

      • Data Integrity

      • End-point authentication

  • SSL

    Neither TCP or UDP provide encryption. To deal with this, the internet community has developed an enhancement for TCP called Secure Sockets Layer (SSL) . This provides all the Security services (encryption, data integrity, end-point auth.) for a transport protocol.

    Note that enhancements on TCP to give SSL are done in application layer, not the transport layer. In then end, everything still relies on TCP.

    Basically, an SSL socket will take the cleartext (un-encrypted) data, encrypt it, and then pass it to a TCP socket.

  • Structure of a Web page

    • An object is any file on the server, such as an HTML file, a PNG, or whatever

    • A web page is a base HTML file plus the objects referenced by this file.

    • The base HTML object references the other objects using URLs .

    • Each URL has two parts :
      • hostname of the server
      • object’s path name

      For example, in http://www.someSchool.edu/someDepartment/picture.gif , the ww.someSchool.edu is the hostname and /someDepartment/picture.gif is the path for the GIF file.

  • Non-persistent and Persistent Connections

    For an application layer protocol, the usual procedure is :

    1. client process requests a connection

    2. server process sends a message back to say “OK”

    3. The actual protocol starts and objects are transferred.

    Now, the way that objects are transferred from server to client describes if the connection is persistent.

    In case all the files are transfered using the same connection, it’s said to be persistent.

    If for each file, a new connection is made, it’s non-persistent.

  • Time needed for fetching

    

    Here, RTT is short for “Round Trip Time”

    Since there are three lightweight message streams sent before the transfer, this is called a “three-way handshake” . Each of these message streams need $\text{RTT}/2$ time.

    This is for a non-persistent connection. This used to happen in HTTP 1.0

    With a persistent connection, the first RTT happens only once, not for each object. This is what would usually happens for a GET using HTTP 1.1 .

  • Pipelining

    While requesting multiple objects in a single connection is better than the non-persistent alternative, there’s an even faster method.

    Instead of waiting for the transfer of the first file from the server to the client to complete, before the client can ask for another file, the client could not wait and just ask many times.

    This is pipelining. By the time the first file is transferred, the second request has already arrived, and so the second file’s transmission starts right away.

  • HTTP

    The great “Hyper Text Transfer Protocol” …

    There are 2 types of HTTP messages :

    • Request messages

      Theses are the messages sent by the client process

      For example,

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

    • Response messages

      Messages sent by server process

      For example :

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

  • HTTP request messages

    

    Here, sp just means “space” , cr means “carriage return” (\r) and lf is “line feed” (\n)

    • method

      • GET : fetches an object based on requested URL

      • POST : still fetches an object, but also uses the values of input fields in a “form” element to tell the server what to return.

      • HEAD : Similar to GET , but the object body is left out in the response. This is used for development purposes

      • PUT : Used to upload objects to Web servers.

      • DELETE : Used to delete an object on a Web server

      • PATCH : Fixes an object

    • URL

      This is the path of the object on the server.

      For example, /somedir/page.html

    • version

      This is the HTTP version that you want to use.

      For example, HTTP/1.1 .

    • Header fields

      One popular field is Host , in particular, the destination host. For example, Host: www.someschool.edu You may think this is unnecessary when there’s already a TCP connection, but it’s used by Web proxy caches.

      Another popular header field is Connection . This specifies whether to close the connection, or keep it open. For example, Connection: close

      Two other headers are User-agent that is the browser type that is making the request (e.g. Mozilla/5.0 ), and Accept-language that specifies the language (e.g. fr for French) to return the web-page in (if that translation is available) .

      The last one is a “content-negotiation” header.

    • Entity body

      This is empty for a GET request, while filled for a POST request. Basically, the values entered in the form fields from where the POST request originated.

      Note that a form is not just limited to POST. It can also use GET, in which case the values are attached to the URL itself, delimited by some special character, such as ? .

  • HTTP response messages

    

    • version

      The same are version field in a request message. For example, HTTP/1.1

    • status code and phrase

      Indicates the result of the request. Some examples are :

      • 200 Ok : everything went correctly and information is sent back.

      • 301 Moved Permanently : Requested object has been moved on the server to a new location. The new URL will be provided in the Location: header of the response

      • 400 Bad Request : Generic error when the request couldn’t be understood by the server.

  • Cookies

    

    If you want the server to remember a client, it can assign each client an ID and send back a “set cookie” header, such as :

    Set-cookie: 1678

    When this cookie is recieved by the client’s browser, it adds it to a cookie file as a hostname: cookie pair. Then, for future requests by the client, the cookie is added in the request as Cookie: 1678 .

    Although cookies make the whole experience easier for the user, it can also be considered as a breach of privacy, since the database can store information about the user.

  • Web Cache / Proxy server

    Similar to the cache in a computer, a proxy server keeps copies of recently requested objects from a actual server.

    

    Companies and institutes use this a lot since the companies’s devices will not want to connect to all of the internet, but mostly the institute related servers

    Ok, but how does a cache actually help. Consider this network :

    

    The 15 Mbps access link is part of the access network for the institution as a massive “end” system.

    Suppose the devices of the institute, all combined request stuff from particular set of servers at a rate of 15 requests per second, with each request being about 1Mbit in size.

    Then, the rate at which data need to be tranferred on the access link is 15Mbps , which is the maximum capacity that the access link can provide. Thus the traffic intensity is 15Mbps / 15 Mbps = 1 , barely at the edge. This will of course cause queue delays, on average, in minutes. Meanwhile delay for the LAN links will be just, say 0.01s

    To avoid this, rather than upgrading the access link’s speed (a costly thing), the institution can set up a web-proxy.

    The hit rate for the proxy will be (usually) 0.2 to 0.7 . Let’s take the scenario of 0.4. This means that the traffic intensity on the access link comes down to 0.6 which, considering the exponential relationship of traffic intensity and queue delay, is pretty good. It reduces the time from minutes to just milliseconds.

    Then, the only relevant delays are the internet delay and the delay due to the LAN, say 0.01s.

    Let’s also assume that the requests that are missed suffer a combined delay of 0.01s due to the LAN and the access link.

    Thus, the average response time for the end user is :

    $$0.4 \times (0.01 s) + 0.6\times(2s + 0.01 s)\\ = 0.01s + 0.6 \times 2s \\= 1.21s$$

    

  • internet delay

    Just to recap, it is the delay in the packets transferred to the first router in the access network (usually in the ISP office) .

  • Conditional GET

    This is related to how to know that you have to update a web cache.

    Unlike in computer architecture, the contents of an object on a server can change since multiple users are interacting with it asynchronously. So when a user requests an object, already stored in the cache, we don’t actually know if the object data is correct (recent) or not.

    To solve this, the web cache must update its data regularly. This is done using conditional GET.

    For example, suppose a user want to get some object, it send a GET message like this to the cache :

    GET /fruits/kiwi.gif HTTP/1.1
    Host: www.exoticqecusine.com

    Then, this message is forwarded to the server from the cache.

    The server responds,

    HTTP/1.1 200 OK
    Date: Sat, 3 Oct 2015 15:39:29
    Server: Apache/1.3.0 (Unix)
    Last-Modified: Wed, 9 Sep 09:23:24
    Content-Type: image/gif
    
    ....data....

    The cache of course forwards the message, and caches the object, but now it also knows the Last-Modified field. This is used for the conditional GET.

    Now, when another user, a week later wants to get the same object, rather than just sending the cached object, the web-cache first verifies if the object is latest. To do this, it sends a conditional GET message to the sever :

    GET /fruit/kiwi.gif HTTP/1.1
    Host: www.exotiquecuisine.com
    If-modified-since: Wed, 9 Sep 2015 09:23:24

    If the object on the server was not modified, then the server sends this response :

    HTTP/1.1 304 Not Modified
    Date: Sat, 10 Oct 2015 15:39:29
    Server: Apache/1.3.0 (Unix)

    There is no entity body attached and thus, there is no extra load on the link due to this message.

• Electronic Mail

  • The 3 components involved

    • User agents

    • Mail servers

    • Simple Mail Transfer Protocol (SMTP)

  • Mail server structure

    There are 2 main things :

    • mail queue

      This is a queue of mails to be delivered to other mail servers and eventually to the user agents connected to that server.

      If the other mail server is down for a mail, then it’s just put back into the queue. Re-attempts are done usually at intervals of 30s

      If a mail stays for too long (usually many days) in the mail queue, it is rejected and the user that wrote the mail is notified through yet another mail, generated from the mail server ofc.

    • User mailbox

      This is a list of mails for a particular user, namely their inbox . The moment that the user opens gmail or outlook, the mails in the user mailbox are sent to the user agent (user device).

  • Direct Server-to-Server connections

    There are no “intermediate” or “central” mail servers. There is no hierarchy at all. The mails in a mail server will only be sent to the destination directly using TCP. They won’t be forwarded to a bigger mail server.

  • Restriction on data format

    Unlike HTTP which can handle any arbitrary binary data, SMTP can only handle 7-bit ASCII characters.

    So, everything has to be converted to ASCII strings before sending, including images, audio, etc.

    Then the strings must be encoded back.

  • Just like HTTP, SMTP has a client (sender) side and a server (receiver) side.

  • Actual protocol :

    This is done in 3 parts

    • SMTP Handshake

    • Mails

    • Closing

    These stages aren’t formal. I just came up with it.

  • SMTP Handshake

    Suppose there are mail servers A (crepes.fr) and B (hamburger.edu) and A wants to send mails to B.

    First, a TCP connection is established. Then we proceed with the handshake.

    B first introduces itself and tells its status .

    220 hamburger.edu

    To this, A introduces itself as

    HELO crepes.fr

    Then B greets A as

    250 Hello crepes.fr, pleased to meet you

    I’m not making this shit up. This is the actual protocol.

    This marks the end of the handshake.

  • sending Mails

    After the handshake, A tells B that there is a mail from a user

    MAIL FROM: <alice@crepes.fr>

    Then B checks if the sender is ok as

    250 alice@crepes.fr ... Sender ok

    Then, A specifies who the mail is for (the recipient )

    RCPT TO: <bob@hamburger.edu>

    Again, B checks if the receiver is ok.

    250 bob@hamburger.edu ... Recipient ok

    Note that there might be multiple receivers, all connected to the same server B. In such a case, the last 2 steps can repeat.

    Finally, A asserts that it’s going to send the contents of the mail as

    DATA

    To which B replies as

    354 Enter mail, end with "." on a line by itself

    What this message means is that A can start sending data, and to end the data section, it has to send just a “.’” alone on a line.

    A then sends the data as

    Do you like ketchup?
    How about pickles?
    .

    The last line has the “.” needed to end the data section.

    To this B replies

    250 Message accepted for delivery

    This whole process happens for all the mails that are to be sent from A to B. These can have different sender, receivers, etc.

  • Closing SMTP connection

    Once all the mails are sent, A sends

    QUIT

    And finally, B replies

    221 hamburger.edu closing connection

  • Mail message formats (headers)

    Perpheral information for a mail is the metadata about the mail, such as the “from”,”to” and “subject” fields.

    Some of this metadata is explicitely taken care of by SMTP, such as through the “MAIL FROM” and “RCPT TO” fields from the client side.

    But it’s also a good idea to have the full metadata using headers. For example :

    From: alice@crepes.fr
    To: bob@hamburger.edu
    Subject: Searching for meaning of life.

    After these headers you need to leave a blank line and then start the body.

    Of course all this is still inside the “DATA” section of the actual mail, as done by SMTP.

  • Mail access protocol

    The reciever end system cannot just get the mail from his server the moment the mail pops in his mail box (inside the server) . Instead, the server “serves” the mail on-demand .

    To do this, you can of course NOT use SMTP, since it’s a push protocol.

    So, you need a different protocol. Popular ones are

    • POP3

    • IMAP

    • HTTP

  • POP3

    The Post-Office-Protocol (3) works like this :

    • authorisation

      • The receiver user agent (call it B) establishes a TCP connection with the mail server (call it M) on port 110

      • M send a +OK POP3 server ready to indicate it’s available.

      • B sends the username as user bob (“bob” is the user name)

      • M responds +OK

      • B sends the password as pass hungry (here, “hungry” is the password)

      • M responds +OK user successfully logged on

      Note that the responses from M will either start with +OK indicating .. an OK execution, or with a -ERR indicating that the execution of last message by the user B didn’t happen correctly.

      For example, if you make a spelling mistake in a keyword M will give an error.

    • transaction

      This is when the actual transfer of mails happens.

      • B starts with list .

      • M reponds with a list of indices for the mails and their sizes in KB . At the end, there will be a single dot .

        1 498
        2 912
        .

      • Then, B will try to retrieve mails from M. To do this, it issues the retr command as retr 1

      • Then, M will send the data for the mail indexed 1 (as in the output of list) . This will be followed by a singe dot on a line to mark the end.

      • Another thing that B can do is mark mails for deletion from M once the conversation is done. For example, if B issues dele 1 , then M will remember that it has to delete the mail that was indexed 1 once this session is closed.

      • There will usually be a chain of retr and dele commands.

      • Once all that is done, B issues quit

      • To that M responds +OK POP3 server signing off

    There are some issues with this method.

    One big issue is of multiple devices for the same user. If the user who uses agent B also uses agent C, and B downloads the mails from M and deletes them, then C will never get the mails. So, the inbox will depend on the device.

    The paradigm where B downloads and deletes is called the (guess what) .. the download-and-delete method.

    Another paradigm is download-and-keep where B will download the mails, but not delete it. This of course means that the mail server needs to store the mails permanently … not nice.

  • IMAP

    This is a more complex and more flexible protocol that POP3. One big feature it has is that of folders .

    Every mail is kept is some “folder” in the mail server. When a mail first arrives, it enters the receiver’s INBOX (the same as mail box) folder on the server.

    • The recipient can move the mails to different folders and create new folders.

    • Of course, the recipient can also read and delete the mails.

    • Moreover, the recipients can also search for mails in a particular folders based of different criterion. Of course, simple listing is also possible as a tiny subset of all the things this feature enables

    • The recipient can also obtain only parts of the mail rather than the full mail, unlike in POP3. This allows for things like GMail to be built easily.

  • HTTP for mail access

    This is what we call “web based e-mail” . Do note that only the mail access (and maybe the transmission of mail from A to its mail server) is through HTTP. The mail servers still interact using SMPT.

    You already know how HTTP operates.

    Now all you have to do is just first get an object from the mail server M that describes the existing mail, download the mails, delete the mails (and update the object enumerating the mails), etc. But this also means you can do weird stuff such as create new mails.. for yourself .. idk what that even does internally. Or update a mail .. some serious legal issues here . Thankfully the mail servers are protected against such things and you can only do operations that applications such as gmail allow you to do, even if you use HTTP directly.

• DNS

  • What does it do ?

    Although each host can technically be identified by its hostname, that isn’t how routers do it. They rely on IP addresses.

    The Domain Name System converts the hostname to an IP address.

  • which layer ?

    This is actually an application level protocol, just like HTTP.

    Unlike HTTP and SMTP, this thing (DNS) usually runs on UDP and not TCP. But you can also make it run on TCP if you want.

  • Network architecture

    You have many DNS servers running at key places.

    The servers are usually UNIX servers and run the Berkely Internet Name Domain (BIND) software.

    Your ISP usually has the IP address of the closest DNS servers stored somewhere in your access network infrastructure. Even your device might have this information.

  • Usage overview

    DNS uses port 53

    When a client wants to get the IP address(es) associated with a hostname, it sends an enquiry to the nearest DNS server

    The query is eventually answered and then the client proceeds with creating a TCP connection (or doing whatever it wanted to do) from the IP address obtained.

  • Nature of mapping

    The mapping from hosts to IP addresses in neither injective, nor a function.

    You can have one host (and thus one IP address) with multiple hostnames, and multiple devices (say, servers) with different IP addresses but the same hostname.

  • Host aliasing

    If a hostname for a server (or bunch of servers) is rather complicated, it might be beneficial to replace it with a simpler host name.

    This is done by host aliasing. The original hostname is called the canonical hostname and the new hostname is an alias for the original. Basically, it points to the canonical hostname, and the canonical hostname points to the IP address.

    This thing is rather important for something like a mail server.

    When you want to connect to any mail server for a mail application, you of course won’t know its actual hostname. Instead, what you’ll know is the alias name, which is the same for all mail servers (physical or virtual) that the mail application uses, for example yahoo.com . You’ll use DNS to get back the canonical hostnames of all of these mail servers and then decide which one to connect to based on your location.

  • Load distribution

    If a content provider has multiple servers and it wants to distribute the load evenly across them, then what it can do is :

    • have a common alias for all the servers

    • on the DNS server side, return the list of IP addresses with that aliased hostname, and rotate it after that (in the database ofc)

    • On the client side, use the topmost IP address in the rotated list

  • How does DNS work ?

    The domain name is made up of parts separated by . . For example, for s='a.b.c' the parts are tokens = ['a','b','c'] . The DNS structure is basically a very big tree with each node having a string made up from tokens[-l:] for some l. The 0th level contains only the empty string.

    Now, the servers in the 0th, 1st and 2nd layers are given names “root servers”, “top level domain servers” , “second level domain servers” .

    Each server is associated with a unique string, namely '.'.join(tokens[-l:]) . This string is called a “zone” . For example, there a root server is associated with zone $\epsilon$ , TLD servers can be associated with zones com , org , edu , etc., and a SLD server can be associated with facebook.com , umass.edu, etc.

    Each server stores the IP addresses of many domains that are “in the zone” . All these domains have the zone string as a suffix.

    But there are also domains with zone as suffix, for which it doesn’t store the IP address and instead stores the hostname of another DNS server that manages a zone with larger string (for example, facebook.com is a larger string than com) . For example, on a server managing zone com, the IP address of www.facebook.com might not be stored. The DNS server will then return the hostname of another DNS server, one that manages the zone facebook.com . All this is very similar to inodes in OS.

    

    Moreover, the local server stores addresses of root servers.

    So, to get the IP address of a hostname, say www.facebook.com , a local DNS server will first ask a root server for the IP addresses of TLD servers associated with com . It will pick one of these TLD servers, and it will then ask that TLD server for the IP address of servers associated with facebook.com . Once again, it will pick one of these servers and will directly ask it for the IP address of www.facebook.com which will be stored in the DNS server.

    

  • Authoritative servers

    Servers that are tasked with managing queries in a particular zone are said to be authoritative of that zone. For a particular query, a server is authoritative of that query if it directly answers it rather than delegating it or through recursion.

    This is assuming there is no cache stuff going on.

  • delegation

    This is when, instead of answering a query by itself, a server gives the address of another server which works with queries more similar to yours. For example, a server authoritative of zone com delegating the query www.facebook.com to facebook.com .

    The new server is called the delegated server.

  • recursive query

    This is when a server delegates a task completely to another server, basically making that server actually do the job , then takes the answer and returns it to the device that the query came from, without that device ever having to communicate with the delegated server.

    

  • iterative query.

    Here, the server returns the hostname or IP address of the delegated server. For example, here the local DNS server is querying iteratively.

    

  • DNS caching

    There are only 400 root DNS servers in the world. You can imagine the kind of inefficiency this would lead to if every DNS query passed through the root servers.

    Thankfully, the DNS servers can cache the answer to the queries that they are supposed to answer (and not delegate) so that the next time a person asks the same query, there’s no need for the DNS server to ask other DNS servers. Note that a server with zone com is not directly authoritative of the query www.facebook.com , but it can still cache it and then answer it.

    In fact, a very small portion of the total number of DNS queries ever reach the root servers.

  • DNS records and messages

    A resource record is a 4-tuple with named fields “Name”,”Value”,”Type”,”TTL” .

    • “Type” field can be one of A , AAAA , NS , MX and CNAME .

    • For type A records, the name field contains a hostname and the value field contains the IPv4 address.

    • For type AAAA , it’s the same as type A except you have IPv6 address.

    • For type NS , the name is a domain and the value is the hostname of a delegated DNS for that domain as the zone.

    • For type CNAME the name is an alias hostname and the value is a canonical hostname.

    • For type MX , it’s the same as type CNAME except that it’s the canonical hostname of a mail server, not just any server. Since usually, a companies mail servers and normal servers have the same alias, the records need different types to distinguish them,

  • For the university network, the hostname (say iitgn.ac.in) is mapped to the IP address dynamically using DMCP . This is done automatically when you connect to WiFi or Ethernet . Moreover, even the IP address for your device is decided by this.

• BitTorrent

  • There is a infrastructure node called “tracker”

  • The torrent is basically a bunch of hosts all trying to distribute a file.

  • For $N$ hosts in the torrent, the distribution time in a centralised architecture would be $O(N)$

  • In a P2P architecture, like bit-Torent , the distribution time is roughly $O(1)$.

  • Each device first contacts the tracker to get a list of IP addresses for all the devices in the torrent.

  • Then, it requests parts of the file from a fixed number of peers. Some devices will actually transmit.

  • Now, it also measures the download rate from each device. The top 4 peers (ones with highest rates) are called unchocked peers.

  • When the device wants to contribute back (upload) , it also picks another peer randomly that is “optimistically unchocked”

  • The unchocked and optimistically unchocked peers are ones that get data from the said device, while other peers don’t.

  • To decide what part of the file to upload, the device will use a rarest first policy, i.e. the part that is present in the least number of peers is uploaded in the torrent.

• Dash

  Dynamic Adaptive Streaming over HTTP (DASH) is a method in which videos are partitioned into parts, for all versions (different bitrate for each version).

  The reciever get the appropriate version of a part based on the download speed, the excess (not being played right now) number of parts already recieved, etc.

  The different versions are specified by URLs .

  All the information is written into a manifest file.

• CDN

  • Content distribution networks are usually used for video data.

  • Some CDNs are private. For example, the CDN for YouTube is owned and maintained by Google.

  • Some CDNs are third-party. That is, they distribute content owned by other companies through their network. For example, Akami, Limelight and Level-3 operate using 3rd part CDNs

  • CDNs can either “Enter deep” , that is, have their servers are on the access ISP networks directly.

  • Or CDNs can “Bring Home” the ISPs by having their servers on IXPs

  • For third party CDNs, they must intercept the requests with hostname of customer company and then send the video on the company’s behalf. This happens by using one of the customer company hostnames (usually a domain associated with the actual videos and not just the company’s general web services, like a website) as an alias for the third party DNS server’s hostname.

  • Do note that once the DNS flow has been handed to the CDN provider, the provider’s DNS servers must also figure out which CDN server should the user must be connected to. This is done by a “Cluster Selection Strategy”. The CDN provider’s DNS server will already know the IP address of the person requesting the video. This can then be used to find the location and locate a geographically close server and send its IP address back.

• logical connection

  This is the view of the connection from the application’s perspective.

  Although A and B may be connected by a complicated path, from the application POV, it’s as if they are connected by a single link.

• transport layer is not there in routers

• transport layer protocols provide logical communication between processes, while network layer protocols do it between hosts .

• UDP in brief

  • User Datagram Protocol

  • unreliable (packet loss can happen)

  • connectionless

  • Does process-to-process data delivery (multiplexing and demultiplexing)

  • error checking (checksum)

  • Sometimes UDP segments are refered to as “datagrams”. That is an archaic terminology and should not be used

• TCP in brief

  • Transport Control Protocol

  • reliable

  • connection oriented

  • congestion control

• demultiplexing

  Delivering the data segments to the correct port based on some fields in the segment

• multiplexing

  Encapsulating the data chunks along with header information from various ports.

• Port numbers

  • 16 bit (unsigned) numbers

  • Numbers ranging from 0 to 1023 are “well known port numbers”

  • In Python socket programming, a socket is by default assigned an unused port number that isn’t well known.

  • In Python socket programming, you can bind a socket to a particular port number.

• Connectionless multiplexing and demultiplexing

  • Each segment has a destination port number and source port number

  • There can be multiple devices sending segments to the same port on a device. The devices are distiguished by their IP address by the application , not inherently by the connection.

  • The source port number serves as a return address. It informs the receiving process which port to send packets back to (for acknowledgements and other things).

• creating a TCP connection

  • The server has a “welcoming socket” running at some port, say 12000

  • The client first sends a connection-establishment request, which is just a TCP segment but with the connection-establishment bit set to 1.

  • The connection-establishment request is identified by the OS and sent to the process running on 12000 for further processing.

  • The process running on 12000 then creates a new TCP connection (and thus, a new TCP socket).

  • A TCP socket is identified by

    • source IP

    • source port

    • destination IP

    • destination port

    Any segment that matches is demultiplexed to the socket.

    In comparison, UDP sockets are characterised only by the source and destination port numbers.

  • One process can be running multiple threads, each managing a separate socet. So, there is no one-to-one correspondence of processes and ports. It’s only instructive.

• Web servers use the same port (80) for the welcoming socket and the actual TCP sockets.

• UDP checksum

  The checksum is just the 1’s complement of the sum of the 16 bit words in a segment, not caring about overflows.

  Now, at the recieving end, if all 16-bit words are added (including the checksum), the value should be 1111111111111111 (binary).

• Why checksum

  Although some link layer protocols already provide error checking, it’s not ensured that this will happen for every link.

  So, you need an end-to-end level error check.

  This is an example of the “end-to-end principle”.

• UDP length field

  This the number of bytes in the actual UDP segment, not just the application data message. Since UDP header are 4 feilds, each of 2 bytes, the length is 8 more than number of bytes in application message.

• Simple ACK,NAK based RDT

  • Sender

    

  • Receiver

    

  Since the sender cannot react to the red_send event when it is in the waiting state, it is thus a “stop-and-wait” proptocol.

  Flaws :

  • ACK,NAK packets can be corrupted

  • Packet loss is not protected against.

• ACK,NAK and 1 bit sequence number

  • Sender

    

    In case of corrupted feedback or NAK, the sender simply sends the packet again. Otherwise it moves to the next packet.

    The feedback does not have the sequence number. But since this is stop and wait, the acknowledgement can only be for the current packet.

  • Receiver

    

    In case the sender got a corrupted acknowledgement, it will just send the packet again. But the reciever is assuming it’ll send a new packet.

    So, in case the sequence number is not the expected sequence number, just send the acknowledgement for the sequence number again and don’t do anything else.

• Only ACK and 1 bit sequence number

  • sender

    

  • receiver

    

  Here, $(\text{ACK},1)$ is acting as $\text{NAK}$ when sequence number of currently sent packet is 0, and vice versa.

• Dealing with packet loss

  The way to identify packet loss is to have a timeout event on the sender side, with the timer set when you reach a waiting state, or reset when the event fires.

  

  For the receiver, whether the sender sent the packet again due to corruption or due to timeout is irrelevant.

  The protocol built till now is called the “alternating-bit protocol”.

• Utilisation

  This is the fraction of time that the sender is actually transmitting packets.

  For a stop-and-wait protocol, it’s very low.

• Go-Back-N

  • The window size $N$ is the number of (unique) packets from the sender that can be on the wire at any given moment.

  • The range of sequence numbers must be at least $N$ . Usually, it is much larger.

  • Sender maintains an (virtual) array $P$ such that $P[m]$ is the packet with sequence number $m$ .

  • The sender maintains base $b$ which is the sequence number of the oldest unacknowledged packet.

  • The sender also maintains the “next sequence number” $n$ that is the the sequence number it will assign to a packet next time it is asked to send a packet.

  • sender : $\text{RDT}(p)$ (where $p$ is a packet)

    • if $n \ge b + N$ : reject and inform upper layer

    • else :
      • $\text{UDT}(p,n)$
      • $P[n] :=p$
      • if $b = n$ : start timer
      • $n := n+1$

  • sender : timeout

    • start timer

    • for $m = b$ to $n-1$ :
      • $\text{UDT}(P[m])$

  • sender : $\text{rcvpkt}(q)$

    • if $\text{corrupt}(q)$ : do nothing

    • else:
      • $b = \text{getack}(q) + 1$
      • if $b = n$ : stop timer
      • else : start timer

  • The receiver maintains the variable “expected sequence number” $e$ which is the packet it will acknowledge next if it reaches.

  • The receiver maintains the variable $q$ which is the last acknowledgement packet it sent. In case of corrupted packets, it just sends $q$ . This will either increment $b$ or not. If it doesn’t the sender will eventually have a timeout and will send the next packet.

  • receiver : $\text{rcvpkt}(p)$ :

    • if $\text{corrupt}(p)$ : $\text{UDT}(q)$

    • else :
      • $m := \text{getseq}(p)$
      • if $m = e$ :
        • $\text{deliver}(p)$
        • $q := \text{mkpkt}(m)$
        • $\text{UDT}(q)$
        • $e := e + 1$
      • else: $\text{UDT}(q)$

• Simple Repeat

  • No cummulative acknowledgements. Only for single packets.

  • Sender maintains array $P$ and $A$ where $P[m]$ is the packet with sequence number $m$ and $A[m]$ is whether an acknowledgement was received for it.

  • Just like before, sender maintains $b,n$ with $n \le b + N$ .

  • Reciever maintains array $R$ where $R[m]$ is whether or not packet with sequence number $m$ was recieved.

  • Receiver maintains $b',n'$ with $n' \le b'+N'$ .

  • Receiver also acknowledges packets in range $[b'-N,b'-1]$ since there is a possibility of all of previous acknowledgements being corrupted or dropped, causing sender to send packets in that range again, while the reciever base has already shifted.

• Multicasting

  This is when the data sent from a host A reaches multiple hosts $B_i$ .

  TCP, for example, is incapable of multicasting.

• MMS

  The Maximum Segment Size is the maximum amount of application data that can be put in a TCP segment

  It is set by first finding the MTU and then setting it so that

  $$\text{MSU} + \text{H}_\text{TCP} + \text{H}_\text{IP} \le \text{MTU}$$

• MTU

  The Maimum Transmission Unit is the maximum size of a link layer frame.

• TCP buffers

  The send buffer and receive buffer are spaces where the TCP segments are stored.

  

  Each TCP socket has its own send and receive buffers (yes, 2 separate buffers)

• TCP sequence numbers

  The sequence numbers are for bytes rather than TCP segments. The sequence number feild in a TCP segment is the sequence number of the first byte.

• TCP acknowledgement numbers

  This is the next expected byte’s sequence number.

  Note that TCP has a flag called “ACK”. It must be set to 1 for the segment to act as an acknowledgement (or carrying an acknowledgment). Otherwise, it’s simply data.

• Initial sequence number (ISN)

  The initial sequence number is chosen randomly (rather than setting it to 0). This is done so that the acknowledgements for any packets still on the wire from previous TCP connection with the same socket identifier (the 4-tuple) are not mistaken as acknowledgements from this session.

• Retranmission Time-Out (RTO) estimation

  This is probably the most interesting part of this book. The timeout is estimated using exponentially weighted moving averages.

  • Iterative adaptation

    For the segments that are sent once and are then acknowledged, the time from sending to recieving is the RTT for that particular segment. Call it $t_n$ for the $n^\text{th}$ such measurement. These measurements are done not for every segment, but are done so that at any given moment, exactly one segment’s RTT is being recorded.

    From these measurements, you can calculate an EWMA as

    $$T_{n} = \alpha t_n + (1-\alpha)T_{n-1}$$

    Then, from that you can derive a measure of deviation of the estimate $D_n$ as :

    $$D_n = \beta |t_n - T_{n-1}| + (1-\beta)D_{n-1}$$

    All of this finally gives us the timeout interval $I_n$ as

    $$I_n= T_n + 4D_n$$

    The recommended values of $\alpha,\beta$ are 0.125 and 0.25 .

  • Initialisation

    Initially, you set the timeout interval $I_0$ to 1s (according the the RFCs). Then when you get the first measurement $t_1$ , you do $T_1 = t_1$ and $D_1 = t_1/2$ giving $I_1 = 3t_1$ . From there, ther iterative process starts.

  • The EWMA smoothens out the actual measured values.

    

• TCP RDT

  • The receiver send cummulative acknowledgements. The acknowledgedment number is only valid when ACK is set to 1.

  • The receiver can either discard out-of-order segments or buffer them.

  • If the receiver decides to not buffer, it should send the ACK with its $e$ value when it encounters an out-of-oder segment.

  • For delayed acknowledgement, the receiver waits for a bit of time before sending the ACK so that if another in-order segment arrives, it only has to send one cummulative ACK for both. When the other segment comes, it sends the ACK immediately for both.

  • In case reciever is buffering the segments, it can either send selective Acknowledgements (SACK) or just send one acknowledgement when the reciever base is moved (the gaps are filled)

  • The sender, on recieving data from upper layer just sends the packet and increments the next-sequence-number value. If the timer is not running (for example if $n = b$ before receiving data) then it starts it. The timeout interval is the moving average estimate.

  • The sender, on timeout transmits the packet with smallest sequence number that isn’t ACKed only (unlike GBN which sends everything).
    Also, every time timeout happens, the timer is restarted. In some modifications, the timeout interval is doubled.

  • On receiving acknowledgement with acknowledgement number (strictly) greater that $b$ , the base $b$ is set to that number and if there are unacknowledged packets, the timer is started. The timeout interval is (re)set to the moving average estimate.

  • In case SACKs are buffered on sender’s end, then you need to set $b$ to smallest unacknowledged byte’s seq. number on recieving ACK with number more that $b$ .

  • For fast-re-transmit, if you recieve 3 duplicate ACKs (4 counting the original one) then you should also transmit the segment with the sequence number same as ack. number received. This would’ve happened regardless if you would’ve got only a stream of these duplicate ACKs and the timeout happened. Thus “fast” retransmit.

• TCP flow control

  • As the segments arrived in the receive buffer, they are processed at some rate. For the buffer to not overflow, the number of bytes that enter the buffer at any point must be lower that the “receiving window” which is simply the space left.

  • You can compute receiving window size as seq. number of last byte received minus the seq. number of last byte processed.

  • The amount of unacknowledged bytes on the sender’s end (which is basically $n -b$) must always be less that the receiving window.

  • The value of receiving window is sent using the “window” field in the TCP header.

  • In the case that the window value is 0 and the receiver doesn’t send anything after that, the sender could be perpetually blocked since the receiver only reacts. It doesn’t initiate converstation.. and if the sender is also not sending anything.. that relationship is dead.
    To solve this, the sender needs to not take “no” as “no” and still send data, in particular 1 byte of data.

• Creating a TCP connection (for real this time)

  • The client chooses a random Initial Sequence Number (ISN) . The choice of this thing is critical to avoid security attacks and it a research topic.
    The client sends an empty segment with this sequence number and the SYN field set to 1.
    This segment is thus called the TCP SYN segment.

  • The server (process), on receiving the SYN segment, also chooses an ISN. It then send a segment with sequence number set to this “server ISN” and the acknowledgement number set to $1 + \text{client}\text{ISN}$ . The ACK and SYN fields are set to 1.
    This segment is called the SYNACK segment.
    Note that in the old implementation of TCP, before sending the SYNACK segment, the server will allocate the butters and variables for this connection. This is a bad idea and leads to SYN flooding.

  • Finally, on geting the SYNACK segment, the client also allocates buffers and variables to the connection.
    It then sends a segment with SYN feild set to 0, no data, and the acknowledgement number as $1 + \text{serverISN}$ and sequence number as $1+\text{clientISN}$ . This segment may also have a payload. At this point, we’ve entered the usual TCP flow.

  • The next segment from the server will have sequence number $1 + \text{serverISN}$ .

• Closing a TCP connection

  • The client sets the flag FIN to 1 in the last segment.

  • The server acknowledges this segment and continues sending any remaining segments from its side.

  • In the last segment the server sets FIN to 1.

  • The client acknowledges.

  

  Note that the final ACK by the client will of course be a segment in itself. But it will not be acknowledged by the server. The server has already dissolved its socket and any segment with SYN set to 0 will be meaningless.

  So, the client just sends the ACK, waits for some time and closes.

• SYN flooding and cookies

  Just like TCP connection flooding, there used to be an efficient DoS attack called SYN flooding.

  The attacker sends a lot of SYN segments to the server. Since in step 2, the server is supposed to allocate resources for the socket before sending the SYNACK, thus the server gets overwhelmed, leading to DoS.

  To prevent this, run a hash function with a secret seed, using the 4-tuple for the SYN segment (IP and port for source and destination).

  Return the hash value in the SYNACK and require the next segment from the client to have this cookie as data.

  Only once that happens should the server allocate resources for the socket.

  (I wonder .. can’t the attacker just send the ACK without allocating resources then ?)

• RST

  A TCP RST segement is one with RST flag set to 1. This indicates that the port isn’t allocated to any process on the server side.

• TCP cycle for client

  

• TCP cycle for server

  

• TCP congestion control

  

  • For congestion window size $w$ and RTT of $T$ , the throughput can be approximated as $\text{MSS} \times w/ T$ . Thus, the utilisation is $\frac{\text{MSS}\times w}{RT}$ .

  • Slow start :

    • For every new ACK received, $w := w + \text{MSS}$ . Thus effectively, in a RTT, the window doubles.

    • On getting 3 duplicate ACKs in a row (condition for fast-retransmit), set $w_\text{thresh} := w/2$ and $w:= w/2 +3\cdot\text{MSS}$ . Then, enter the Fast Recovery mode.

    • On having a timeout event, do $w_\text{thresh} := w/2$ and $w := \text{MSS}$

    • If $w > w_\text{thresh}$ is achieved, then go to Congestion Avoidance mode

  • Congestion avoidance :

    • For every new ACK, $w:= w + (\text{MSS}/w)$ .

    • For 3 duplicate ACKs, $w_\text{thresh} := w/2$ and $w := w/2 + 3 \cdot \text{MSS}$ . Also, enter the fast recovery mode.

    • In case of a timeout, $w_\text{thresh}:= w/2$ and $w := \text{MSS}$ . Enter the slow start mode.

  • Fast recovery

    • For new ACK, $w := w_\text{thresh}$ and go to congestion avoidance mode

    • For timeout, $w_\text{thresh} := w/2$ and $w := \text{MSS}$ and go to slow start.

    • On getting the same duplicate ACK due to which you got to this mode, do $w := w + \text{MSS}$ .

• An individual router does forwarding (a local operation), while the full network layer (as an infrastructure) does the routing of the packet (end to end).

• Forwarding happens using the forwarding table .

• The forwarding table maps the header values to interfaces (outgoing links) . This is based on PLA (programmable hardware, not a full blown processor.).

• The control plane routing algorithms decide the forwarding tables for each router,

• Usually the control plane is implemented in software, thus “Software-defined networking” or SDN for short.

• The network service model is the set of characteristics (rules) for end-to-end delivery of packets.

• The ATM (yes, Any-Time-Money) network architecture implements

  • in-order packet delivery

  • bounded packet delay

  • guaranteed minimal bandwidth

• The Intserv network architecture provides

  • end-to-end delay guarantee

  • congestion free communication

• Despite internet’s network layer being only “best-effort” (really, no effort), it is adequate.

• When the switching/forwarding is based on link layer header, the packet switch is called a link-layer switch, and is NOT a router, and NOT a part of the network layer

• The structure of a router

  • Input port : This is where the incoming data arrives. Namely, it is one of the ends of a communication link. This is further made up of 3 parts, the physical layer stuff (ADC, for example), the link layer stuff (i don’t even know what happens here), and finally, the forwarding table. The packet’s header is used and the output port is decided here (remember, big combinational circuit, so no need to worry about the data).
    Apart from normal data packets (which go to one of the output ports, there are control packets that go to the routing processor)

  • Switching fabric : This simply connects the input ports to the output ports and passes information based on the output port values decided earlier.

  • Routing processor : This performs control-plane functions, such as changing the forwarding tables.

  • The forwarding table is copied from the routing processor to the input ports using a data-bus separate from the bus for the packets; for example a PCI (Peripheral Component Interconnect) . This allows for deciding the output port at the input port itself, rather than invoking the (central) routing processor.

• Input port processing

  • The forwarding table uses “longest prefix match” to decide the port. Namely, it matches keys with the header to find the longest key which is a prefix of the header (binary ofc). This key’s value then is the output port.

  • The processing happens in two stages, a “match” (finding the matching key) and an “action” (sending the packet to the switching fabric). This “match-plus-action” abstraction is more general and used by many network layer devices.

  • There are content addressable memories called TCAM that are used for forwarding table lookup in constant time.

• Switching

  • Switching can be done via memory, a data bus, or a crossbar switch

  • Memory

    When switching using memory, suppose the AMAT is $T_M$ , giving us a rate of $1/T_M$ packets per unit time, then since in a unit of time, both read and write operations have to be done, thus only $0.5/T_M$ packets are written out to the output ports. Thus, the bandwidth $R$ is bounded as $R < 0.5/T_M$ .

    

  • Bus

    Switching over a databus is faster. The rate of transmission is just the rate of transmission for the bus.

    

  • Crossbar (interconnect network)

    A crossbar switch is intended to be non-blocking. If you have packets on input links A,B that want to go to output ports C,D then this transmission can happen simultaneously.

    

• Queuing

  • We have 3 different rates to worry about now.
    • $R_{in}$ , the rate at which a single input port receives data.
    • $R_{switch}$ , the rate for the switching fabric
    • $R_{out}$ , the rate at which a single output port sends the data.

  • For $N$ input ports, if $NR_{in} \le R_{switch}$ then there will be no queuing in the input ports.

  • Head of Line (HOL) blocking is when a packet in an input port is blocked leading to blocking all the packets behind it even though those packets would not have been blocked otherwise

    

  • Unlike input queues, output queues can form even when $NR_{out} \ge R_{switch}$ when the packets are not distributed equally among the output ports.
    Instead, to ensure no output queueing, you need $R_{out} \ge R_{switch}$ , which isn’t practical.
    So we will almost always have output queuing.

  • Active Queue Management (AQM) alhorithms are those that return a congestion notification to the senders when it is likely that the input queue will be overflowing soon. This is done by
    • packet marking (explicit)
    • packet dropping (implicit)

  • Random Early Drop (RED) is a popular AQM algorithm.

• Packet Scheduling

  • FIFO : Just one queue

  • Priority Queuing

    • Many classes (Type of Service) of packets each having its own queue.

    • The class with more priority gets serviced first.

  • Weighted Fair Queuing

    • multiple classes (TOS) with each having its own queue

    • Each class gets assigned a weight $w_i$ .

    • For $S$ being the set of classes available at the point of decision, the fraction of service that the $i ^\text{th}$ class will get is $w_i/(\sum_i w_i)$ for that iteration.

    • The “service” is measured in the fraction of time for a time slice that packets will be forwarded from a particular class.

    • work-conserving queuing : If a class is missing, skip it in that iteration and go to next class directly. Basically, never be idle. This is automatically because that class will not be in $S$

    • Round Robin is just a special case of WFQ where $w_i = 1 \forall i$

• IPv4 format

  

  • Version number (4 bits) : Is it IPv or IPv6

  • Header length (4 bits) : The options field is variable length so we need to specify the length of the header. Usually it is 20 B only, with no options.

  • Type of Service (TOS) (8 bits) : Binary code for what kind of service is the datagram part of, such as
    • Real time (IP telephony for example)
    • Non-real time (for example FTP)
    • Explicit congestion notification

  • Datagram length (16 bits) : Number of bytes in the layer 2 segment that this datagram encapsulates.

  • Identifier (16 bits) : A segment may be fragmented into multiple datagrams and a datagram into multiple fragments or smaller datagrams (if the MTU is smaller for an output link for example). This field is needed to identify which datagram a fragment belongs to.

  • Flags (3 bits) : One of these flags is “last fragment” which is set to 0 for the last fragment of a datagram and 1 otherwise.

  • fragmentation offset (13 bits) : Needed to distinguish between fragments for the same datagram and reordering them on the receiver host’s end.

  • TTL (8 bits) : This is a number that is decreased every hop. If it reaches 0 before reaching the destination, the datagram is discarded.

  • Protocol number (8 bits) : The transport layer protocol that sent this datagram. For TCP, it is 6 and for UDP it is 17.

  • Header checksum (16 bits) : The same thing as in UDP, except no pseudoheader involved.

• IPv4 fragmentation

  The identifier (16 bits), flags (3 bits) and fragmenation offset (13 bits) are used for fragmentation.

  Since the Maximum Transmission Unit, which is the size of the link layer frame is different based on different link layer protocols (Ethernet and some WAN having different MTU for example) , so the router must fragment a datagram into smaller ones in case its too big for the output link’s frame.

  These fragments are reunited only at the receiver host, and NOT at some router. The routers only forward.

  

• IPv4 addressing

  • The boundary between a router and a physical link is called an interface

  • IP addresses are actually identifiers for the interfaces rather than the hosts.

  • The decimal notation of an IPv4 address is when it’s written as 4 decimal numbers separated by bytes.
    The binary notation is just the 32 bits.

  • A subnet or IP net is a subgraph of the access network.

    

  • The leftmost x bits of an IPv4 address are called the subnet address or network prefix or network portion. This is the same for all hosts in a particular subnet. The number x is variable. The IP address is then written as a.b.c.d/x .

  • In classful addressing, x is only a multiple of 8.
    • if x = 8 : the subnet class is A (largest subnets with 24 bit internal addresses)
    • if x = 16 : the subnet class is B
    • if x = 24 : the subnet class is C

  • Classless Inter-Domain Routing (CIDR) is when x can be anything, not just multiples of 8.

  • An ISP is usually assigned an address block corresponding to a particular prefix. For each organisation inside the ISP network, more bits are specified for the network prefix.

  • Only the network prefix is used in external routing protocols such as eBGP

  • If two BGP speakers are assigned to different ISPs A,B and A acquires B, then the BGP speaker for B can simply advertise the subnet address for A too, in addition to the network address for B. Thus, we have a single prefix for multiple networks. This is called address aggregation or route aggregation.

  • The IP address 255.255.255.255 is for IP broadcast across the subnet. Optionally, routers may send this outside the subnet too.

  • The Internet Corporation for Assigned Names and Numbers (ICANN) allocates the network prefixes for ISPs .
    This organisation also maintains the DNS root servers.

  • ICANN assignes addresses to regional internet registeries. All this combined is the Address Supporting Organisation of ICANN (ASO-ICANN)

• DHCP

  • Inside a subnet, addresses are assigned using the Dynamic Host Configuration Protocol (DHCP). The addresses assigned are intended to be temporary and there is no manual intervention (plug-and-play/zeroconf).

  • DHCP allows a host to learn

    • Its IPv4 address

    • The IPv4 address of the local DNS server

    • The IPV4 address of the first-hop router (aka default gateway)

  • DHCP happens in 4 steps

    • DHCP discovery

    • server offer

    • request

    • ACK

  • DHCP discovery

    client sends a UDP segment with

    • destination port 67

    • 0.0.0.0 as source IP address in IP datagram

    • 255.255.255.255 as destination IPv4 address in IP datagram

    • A transaction ID in the contents of the UDP segment. This ID will be used for all 4 steps.

    This datagram is broadcasted to the whole subnet.

  • DHCP server offers

    Any DHCP server in the subnet responds to the DHCP discovery message with another broadcast (hence 255.255.255.255 as destination IP) and its IPv4 address as the source IP.

    The offer also contains

    • the IP address to assign to the client (yiaddrr),

    • the server ID and

    • the transaction ID that the client sent earlier.

    • The lease time / lifetime in seconds for which the assigned IP address will be valid (can be hours or days)

  • DHCP request

    The client chooses one of the offers and echoes back the offer parameters. This is also done in broadcast (255.255.255.255 as destination IP), with 0.0.0.0 as the source IP address.

    Since the chosen DHCP server IP is echoed back, the other servers stop the protocol at that instant.

  • DHCP ACK

    The chosen server finally broadcasts an acknowledgement UDP segment, echoing the paramters.

  • DHCP full flow

    

  • An issue with Dynamic IP addresses is that it’s impossible to maintain a TCP connection as the client moves.

  • CINFO, CHADDR

  • DHCP proxy

• NAT (NAPT actually)

  • The address space 10.0.0.0/8 is one of 3 portions of the full IP address space that is reserved for a private network. Again, the portion we are talking about contains any IP address with 10 as first 8 bits; for example 10.0.0.1 .

  • The NAT network addresses are not unique over the gobal internet, but unique in the NAT network

  • NAT routers replaces the source ”IP” address for devices in the network and uses its IP address instead.

  • NAT routers also replace the source port for outgoing messages according to the NAT translation table

  • The NAT translation table maps the source “IP address” and port pair to another source port number which the NAT router replaces the actual source port number with before sending out the datagram.

  • For each received datagram, a reverse lookup in the NAT translation table is done to get the actual destination (its NAT network “IP” address) and the actual port.

  • Thus, NAT uses port number to address the hosts in the network. This is a violation of the transport layer protocol’s semantics.
    This also makes it impossible to have servers in a NAT powered network since they need to have fixed port numbers and thus can’t be addressed using port numbers.

  • Public address translation : (src IP a, src port p) → (NAT IP n, src port $q_{a,p}$)

  • Private address translation : (NAT IP n, dst port $q_{a,p}$) → (dst IP a, dst port p)

  • In NAT, only addresses are translated to port.
    In NAPT, both address and port is translated to the NAT port

• ST-2 protocol was to be IPv5 but the initiative was dropped

• IPv6 was envisioned because IPv4 address space is depleting.

• IPv6 format

  

  • Traffic class is the same as TOS in IPv4

  • Next hdr is the same as protocol feild in IPv4

  • Hop limit is just the TTL

  • Playload length is an unsigned 16 bit integer giving number of bytes in the playload

  • The flow label is an identifier for the flow that this datagram belongs to. A flow is simply a stream of datagrams that when combined, transmit a message; the same as in TCP basically.

  Note that IPv6 does not allow for fragmentation.

  It also doesn’t do error correction. This is taken care of by TCP or UDP

  There is also no option field explicitely present. Instead, the “next hdr” part actually describes the meaning of the next header that will be encountered in the datagram while going up the network stack, and can also be the encoded value for options. So, there are variable size options, but no explicit header length field. Instead, the protocol part is used for that (not the length, just the existence).

  IPv6 standard header is 40B .

• Tunneling

  This is a trick that allows IPv6 speaking routers to talk with IPv4 speaking routers. Basically, the IPv6 router encapsulates the IPv6 datagram into an IPv4 datagram (by adding an IPv4 header). This wrapper datagram is then transmitted by the IPv4 speaking networ until it reaches an IPv6 speakinng router where it is un-encapsulated.

  

• OpenFlow SDN

  Here, rather than routers, we deal with generalised packet switches that can do a lot more than forwarding.

  OpenFlow is a successful standard that is used for such generalised packet switches.

  The forwarding is done by a general match-plus-action principle.

  You can match based on information from transport, network and link layer rather than just the network layer like in a router.

  

  • For actions, you can do

    • forwarding to a particular output port

    • broadcast over all ports

    • Encapsulate the packet ant send to the remote controller

    • Drop the packet (default action, if nothing specified in flow table)

    • Modify any of the feilds for layers 2,3,4; except for the IP protocol / next hdr feild.

  The match-action pairs make up the flow table for the packet switch.

  

  The flow tables are in-turn updated by the remote controller that runs on software, rather than hardware like the packet switches.

  Thus, the flow tables are like API for the packet switch that the remote controller uses to program.

  Just like modern routers, an OpenFlow devices uses TCAM for the matching.

• per-router vs logically centralised

  • per-router control is when the routing algorithm runs in the routing processor rather than a remote controller. Examples : BGP, OSPF

  • Logically centralised control is when it the routing algorithm runs is a central remote controller. Example : OpenFlow and SDN

• Control Agent

  A control agent (CA) is a part of the router whose job is to communicate with the central controller.
  CAs don’t interact with each other and don’t actually compute forwarding tables.

• Infinity weight trick

  When two routers $a,b$ are not connected directly by a communication link (i.e. $\{a,b\} \not\in E$), we can model that as $c(a,b) = \infty$ where $c:V^2 \to \mathbb{R}_{\ge 0}$ is the cost function.

• Centralised and Decentralised routing algorithms

  • A centralised routing algorithm is one where all the information about the graph is known beforehand and then the routes are computed. Basically, you need to be aware of the states in which the links are, hence “Link State” (LS) algorithms.

  • A decentralised routing algorithm is one where the changes in routes in response to new local information are done locally. The calculation is thus distributed and iterative. The full link state information is not known. Only the previously computed distances from a given node to other are known at a particular node; namely the distance vector (DV) .

• static vs dynamic

  A static routing algorithm changes the routes very slowly (mostly due to human intervention) as opposed to a dynamic routing algorithm that changes it fast.

• In a load sensitive algorithm …

  the link costs change as a function of the flow.

• Link-State algorithm

  • Since $c(u,v) \ge 0$ so, to find the shortest paths to any node, the LS approach is for all routers to flood the LS information, and the for all routers to individually run Dikstra’s or Prim’s shortest path algorithms to computer their own forwarding tables. This works well for load insenisitive networks, but not for our case.

  • A solution is to have only one router update its forwarding table at a time, and flooding the network with LS information again after that.

  • An issue with this is something known as Floyd Synchronisation, which is a tendency of the routers to synchronise on their own.

• Bellerman-Ford equation

  Let $d(a,b)$ be the smallest path distance from node $a$ to $b$ . Then, the Bellerman-Ford equation says that

  $$d(x,y) = \min_{v\in N(x)} (c(x,y) + d(v,y))$$

  Using this, we can set up an iterative solution.

  Let $d_z(x,y)$ be the known smallest distance from $x$ to $y$ by the node $z$ .

• DV algorithm

  • $d_y(x,x) := 0 \ \forall x,y \in V$

  • loop :
    • for $y \in V$ :
      • if $D(y,z)$ changed in last iteration for any $z$ :
        • for $x\in N(y)$ :
          • $d_x(y,z) := d_y(y,z) \ \forall z \in V$
    • for $x \in V$ :
      • $d_x(x,y) := \min_{z\in N(x)} (c(x,z) + d_x(z,y))$

  

• count-to-infinity

  The DV algorthm suffers from this issue.

  Suppose you have the network described in this picture :

  

  The DV algorithm has reached an equilibrium where z is routing to x through the interface towards y.

  Now, suppose the $c(y,x)$ changes from 4 to 60, then $y$ will first try to re-compute $D_y(y,x)$ . This will fail since $D_y(z,x)$ is 5, making $D_y(y,x) = 6$ . Then, $z$ will update $D_z(y,x):=D_y(y,x)$ after $y$ sends it the distance vector and then update $D_{z}(z,x) = 7$ . Later, we will get $D_y(y,x) = 8$ and so on. This will keep on going till we eventually reach $D_y(y,x) = 60$ and $D_z(z,x)= 61$ .

• Poisoned reverse

  To avoid this extremely slow convergence due to the count-to-infinity issue, we should use poisoned distance reverse. Basically, if for the smallest path to a node $c$ , some node $b$ is going through a node $a$ , then $b$ should tell $a$ that $D_b(b,c) = \infty$ even though it isn’t.
  Another way of saying this is that $b$ tells $a$ to not route through it to reach $c$ ; hence the $\infty$ distance.

  Unfortunately, this isn’t enough.

  Consider this network :

  

  You will have a loop between $w$ and $y$ now when $c(y,x)$ changes to 60 suddenly.

• Autonomous Systems

  • An autonomous system (AS) is a network where all routers speak the same routing protocol and form a connected component for that protocol.

  • An AS can contain multiple sub-nets.

  • Every AS gets an Autonomous System Number (ASN) assigned by ICANN.

• OSPF

  • Open Shortest Path First

  • This is an intra-AS routing algorithm.

  • This uses LS brodcasting and then Dijsktra’s algorithm in each router (classic LS strategy)

  • The broadcasts happen periodically regardless of whether the LS info for a certain router has changed.

  • OSPF adverticements are carried directly using IP

  • OSPF is actually treated as a transport layer protocol by IP, and is assigned the protocol number 89

  • OSPF implements reliable message tranfer and link state broadcast

  • OSPF routers additionally check if the attached links are active by sending a HELLO message to the neighbourhood routers.

  • Exchanges between routers can also be authenticated in OSPF allowing only trusted routers to run this protocol.

  • OSPF authentication can either be done is plaintext (simple mode) or with MD5 encryption (MD5 mode)

  • When a router multiple paths to another node with the same distances, then both paths can be used (using RR for the traffic, for example)

  • Multicast OSPF (MOSPF) is an extension over normal OSPF (which is already multicast btw)

  • OSPF also allows for heirarchy

    

    • code

      graph G {
          rankdir=TD
          A [shape=square color=green]
          B [shape=square color=green]
          C [shape=square color=green]
          D [shape=square color=green]
          
          A -- a [color=green]
          c -- C [color=green]
          a -- d
          a:sw -- b:ne
          d:sw -- c:ne
          b:se -- c
          a:s -- c:n
          subgraph{
              rank=same;
              B--b [color=green];
          }
          subgraph{
              rank=same;
              d--D [color=green];
          }
          subgraph{
              rank=same;
              b--d [label="back bone"];
          }
      }

    You can split the AS into a bunch of areas, with each area having some area border routers and the normal routers.

    The area border routers are all connected to a back-bone area which routes traffic between different areas.

    The back-bone must contain all area border routers, and hence no peering between the areas; everything passes through the backbone.

    The back-bone may also contain non-border routers too.

• BGP

  • Multiple subnets are handled by a single BGP speaker.

  • BGP speakers communicate over TCP

  • When two communicating BGP speakers are part of the the same AS, it’s called an iinternal BGP (iBGP) connection. Otherwise, external BGP (eBGP).

  For the remaining portion, consider this network :

  

  • x is the network prefix of a subnet that is newly added. We want its existence to be known to the whole world.

  • The BGP speaker 3d tells and 3a,3c through iBGP about the existence of this prefix. This is iBGP. 3a and 3b tell 3b then. The message that is passed can be denoted as simply x for now.

  • 3d tells 1d through eBGP of the existence of x . This is done via the message 3d AS3 x which reads “x exists, and it can via the AS path with only AS3 in it. To start the path, hop to 3d” . Similarly, 3a sends 3a AS3 x to 2c

  • 1d propagates the 3d AS3 x message throughout AS1 using iBGP. Thus, all the BGP speakers in AS1 will now route packets to x through 3d (the next hop router).

  • 2c propagates the 3a AS3 x message in AS2 using iBGP .

  • 2a sends 1c the eBGP message 2a AS2 AS3 x which reads “x exists and can be reached by the AS path AS2,AS3 . To start the path hop to 2a (me)”.

  • 1c propagates the 2a AS2 AS3 x message through iBGP to all of AS1 . Now, the routers in AS1 must decide which route to choose. Route selection is done based on these factors in decreasing priority
    • local (ISP) preference (biggest priority)
    • length of AS path (AS2 AS3 vs AS3).
    • length of path to next-hop router (2a vs 3d) . This is called hot-potato routing.
    • BGP identifiers

    In this case, assuming local preference allows both routes, the 3d AS3 x route will be chosen as it has smaller AS-PATH

  • AS-PATH, a sequence of the ASNs for the ASs in the path is a BGP attribute

  • Similarly, NEXT-HOP, the IP address of the next-hop router is a BGP attribute

  • A BGP route consists of the network prefix and several BGP attributes; AS-PATH and NEXT-HOP being two very important ones.

  • Once a BGP route is selected by a router, it uses its forwarding table to learn which interface does the NEXT-HOP value get mapped to. Then, it inserts the network prefix and this interface as a pair in the forwarding table

• IP anycast

  The DNS root servers for a particular DNS root server organisation (out of the 13 that there are) all have the same IP address. For example, 8.8.8.8 is an IP address for many physical DNS servers, all of which virtually/logically appear to be a single entity.

  To make this happen, we need multiple subnets; potentially in different ASs; that have the same subnet address (prefix).

  In such a scenario, when these subnets are advertised and any BGP speaker gets two routes; each originating from a different subnet, but having the same prefix; then these routes are simply treated as multiple paths to the same destination. The BGP route selection protocol operates as usual, and the “best” route is selected; and thus, the “best” subnet, without the BGP speaker having any idea about the existence of multiple subnets with the same prefix.

• Role of policies

  The ISP can have a policy for example, to only route traffic with a customer or domestic sub-net as source or destination, and not allow free-riding.
  So, when it gets a BGP advertisement from a subnet that is not a customer, it will gladly spread it via iBGP but not through eBGP since that’s basically telling other ASs “hey, look at this route to this subnet that I don’t server. I can take you to this subnet. Just hop on the NEXT-HOP router that is inside my network. I’m a very altruistic ISP and I don’t care about all the extra link utilisation, traffic intensity and packet loss that routing your traffic through my network will cost me.” .. you get the point, right ?

• SDN

  

  The controller acquires information from the controlled devices using protocols such as OpenFlow and SNMP. This is south-bound API

  The state management layer is where information from multiple of the SDN controllers are combined.

  The API through which the controller interacts with the applications that actually do stuff, such as running the Dijkstra’s algorithm for example, are called the Northbound API. This can be a graph database, or REST, or anything really.

• OpenFlow

  • A southbound API

  • Runs on TCP port 6653

  • The types of messages that can be sent from the controller to the switch are:

    • Configuration (”switch, please set these parameters”)

    • Modify-State (”switch, update your flow table to this”)

    • Read-State (”switch, read and send your flow table’s statistics and counters”)

    • Send-Packet (”switch, send this specific packet from this specific output port”)

  • The messages that can be sent from switch to controller are

    • Flow-Removed (An entry in the flow table has been removed)

    • Port-Status (An output port has shut down or is malfunctioning)

    • Packet-In (I didn’t have a match for the address in this packet, help me)

• ICMP

  • Internet Control Message Protocol

  • This is for the communication between routers as opposed to through them.

  • ICMP messages are encapsulated in IP datagrams with port number of 1

  • Each ICMP message has a type number and code number.

  • Each ICMP message contains the first 64 bits (first two lines) of the IP datagram that triggered this message.

  • ICMP messages

    type	code	Description
    3	0	destination network unreachable
    3	1	destination host unreachable
    3	2	destination protocol unreachable
    3	3	destination port unreachable
    3	6	destination network unknown
    3	7	destination host unknown
    4	0	source quench (congestion control)
    0	0	echo reply (to ping for example)
    8	0	echo request (like in ping)
    9	0	router advertisement
    10	0	router discovery
    11	0	TTL expired (like in traceroute)
    12	0	IP header bad

  • ICMP was designed for IPv4. With IPv6, they have added more messages, such as “Packet too big” since IPv6 doesn’t have fragmentation and “unrecognised IPv6 options”.

• SNMP

  • Simple Network Management Protocol

  • This is a protocol used by (human) network administrators to debug network issues.

  • The key components of network management are:

    • The managing server (usually with a human in the loop) running in a Network Operations Center (NOC).

    • The managed devices and managed objects (hardware or software parameters) inside it.

    • The management information base (MIB), which is a store of several managed objects/parameters (such as counters, descriptive information, routing path to a destination, etc.) inside a managed device.

    • The network management agent (basically CA for SNMP) is a process running in the managed device that communicates with the server.

    • The network management protocol allows the management agent and server to communicate.

  • MIB objects are specified using a data description language called Structure of Management Information (SMI) .

  • Related MIB objects are gathered into MIB modules.

  • SNMP usually runs in a request-response mode where the server first sends a request (to query or modify MIB objects) to the agent which then performs some action and sends back a response.

  • When the agent sends the server a message by itself to inform about an exceptional event that has occured, it’s called a trap message.

  • SNMPv2 messages are simply called PDUs (protocol data units).

  • A manager can also ask another manager for information.

  • Different PDU types

    • The GetRequest , GetNextRequest and GetBulkRequest query PDUs are sent from manager to agent (or another manager) to query for MIB vales.

    • The SetRequest PDU is sent from manager to agent (or another manager) to set a bunch of MIB objects.

    • A Response PDU is sent from an agent to manager in response to a query or SetRequest PDU.

    • The InformRequest PDU is sent by a manager A to another manager B in response to a query or SetRequest sent by B to A.

    • Finally, there are SNMPv2-Trap PDUs sent by agents to manager when exceptional events occur.

  • The lack of security made SNMPv1 a monitoring protocol rather than a control protocol (rendering the modification part obselete)

  • SNMPv3 focuses heavily on security.

• Key design principles for internet architecture

  • Robustness :

    Be conservative while sending , and liberal while accepting

  • Layering principle :

    The message on system A’s layer N will be transmitted to system B’s layer N, as it is with no modifications. All the stuff done by the lower layers must be removed by B .

  • End2End :

    The actual computation only happens on the end systems.

  • Network is stateless

    Only the end systems manage state.

• Why layering ?

  • modularity
    • reduced complexity for writing code
    • more flexibility in modifying the higher level modules and thus the computer networks
    • standardised interfaces makes development easier

  • functionality reuse :

    A common functionality of a lower layer can be shared by many upper layers

  • Adaptability :

    Mix and match functionalities across different layers.

  Incremental changes are easier to make and accumulate

• peer layer

  Same level layers in end systems that are communicating

• vertical communication

  The communication between adjacent layers on just one end system. Like, between application layer and the transport layer.

• horizontal communication

  Virtual communication between peer layers.

• Protocol layering

  “This is the grouping of communication functions into heirarchial set of layers.”

  • every layer has a different subset of functions

  • every layer relies on the lower layers for more primitive functions

  • every layer provides service to the higher layers

  • Implements a protocol for communication with peer layers (horizontal communication)

• SDU

  Service Data Unit

  This is an input of any protocol for a certain layer.

• PDU

  Protocol Data Unit

  This is the output of the protocol for a layer.

  This is basically the SDU, with a header $\text{HDR}_N$ attached at the front, for the layer $N$ protocol in a network application.

  $$\text{PDU}_N = \text{HDR}_N + \text{SDU}_N$$

  The horizontal communication between peer layer entities (processes for that layer) happen happen by exchange of the PDUs (virtually)

  Note that layer N does NOT make use of $\text{SDU}_N$ .

• Protocol

  The set of rules that govern data communication between peer layer entities

• Encapsulation

  The PDU for a layer contains all the information that will be needed for the upper layers to comprehend it. That is, it encapsulates the information and now we can think of it as “just data” in the lower layers.

• Bandwidth is the maximum throughput through a link (the maximum transmission rate).

• Throughput is the actual transmission rate observed through a link bits per second.

• Goodput is the rate of transfer of application layer messages (in bits per second) . Basically Goodput is measured discounting the headers.
  Plus, the data lost due to packet loss is also not “useful” data so it’s not to be included while calculating goodput.

• “link capacity” = “link bandwidth” = “link transmission rate” .

• The transmission delay is the size of packet divided by the throughput (NOT the bandwidth).

• When there’s one router between two devices the transmission delay is $2L/R$

• “Cut through” is when you don’t want to do store and forward. Instead, you store till you have the destination MAC address (6 bytes), then compute the output link and start transmitting without storing.
  This doesn’t allow reliable transmission since you aren’t able to store and compute to see if the data is correct (using Hamming codes or whatever). While in store-and-forward, the transmission would just stop at the first router where eronnous data is encountered, in cut-through, the data is forwarded.
  To somewhat solve this, you can store extra 64 bytes for figuring out if there is an error (using checksum or something)

• CFS (completely fair scheduler) was built for networks and later cam to linux kernel. This aims to reduce the response time.

• Ingress link is “Incoming” link.

• The Egress link is “outgoing” link.

• The first thing that happens when a packet reaches a outer is the ingress processing.

• There CAN be queuing delay at the source. This happens when we are transmitting only once all packets are prepared.

• read a bit about sequence diagrams in the context of delays

• Ingress processing can happen even when egress processing is going on. Basically, there is some pipelining in a router.

• Practice end to end delay questions, a LOT.

• We have two kinds of throughput : instantenous (used for identifying peak bit rate (PBR)), which is measured over a small window and average throughput, that is measured over a longer window.

• Switching techniques

  • Message switching

    This is similar to packet switching except that you send the full thing all at once, with no packetisation.

    There is also resource reservation on the routers (similar to that in circuit switching).

    For example, telegram messages were transmitted like this.

    This also uses store and forward architecture.

  • Circuit switching is “cut-through” (just the opposite of store-and-forward)

  • CDM

    Similar to TDM and FDM, there is code-division-multiplexing. In this, you encode 1 as some vector $v_1$ and 0 as $v_0$ for each connection. Now, we want all these vectors to be orthogonal, so that you can do superposition and transmit the resultat vector. That vector will be decomposed at the reciever end, with no loss in information.

  • Wavelength-Division-Multiplexing is just FDM but in fiber optics.

  • Synchronous TDM is when there is a proper RR scheme

  • Statistical TDM is when the sender only transmits when it is ready. This happens in Ethernet.

• Ingress is incoming and egress is outgoing data

• Organisation names

  • IEEE : Institute of Electrical and Electronical Engineers
    Manages Data link and Physical layers

  • IETF : Internet Engineering Task Force
    Manages Network and Transport layer (IP/TCP) and RFCs

  • W3C : World Wide Web Consortium
    Manages application layer protocols

  • ISO : International Organisation for Standardisation
    Maintains other standards. A bit outdated.

  • ITU : International Telecommunication Union
    Manages protocols related to telecommunication

• A computer network is an infrastructure that facilitates communication across devices.
  The infrastructure encompasses hosts, switches and the medium too.

• unit prefixes

  Name	Symbol	Value
  kilobinary	Ki	2^10
  kilo	K	10^3
  megabinary	Mi	2^20
  mega	M	10^6
  gigabinary	Gi	2^30
  giga	G	10^9
  terabinary	Ti	2^40
  tera	T	1000^4
  petabinary	Pi	2^50
  peta	P	1000^5
  exabinary	Ei	2^60
  exa	E	1000^6
  zetta	Z	1000^7
  yotta	Y	1000^8

• Internet is big endian

  meaning that the address of a word is the byte addess of the MSB in the word. For little endian, it is the LSB.

• 3 aspects of protocols

  • syntax (data format and physical modulation)

  • semantics (procedure for communication)

  • sequence (frequency and order)

• Principles of internet architecture

  • robustness principle

    Be conservative in what you send and liberal in what you accept

  • Layering principle

    layer N PDU on receiving side is transmitted exactly the same when it reaches layer N on the other side.

  • End2End principle

    Network is stateless (dumb) and hosts manage states (intelligent)

• Why layering

  • Modularity allows for
    • reduced complexity when focusing on smaller problems
    • more flexibility
    • standardised interfaces

  • functionality reuse (a service provided by a lower layer protocol can be used by multiple higher layer protocols)

  • Adaptability

  • Easier incremental changes

• Encapsulation

  $\text{PDU}_{N} = \text{H}_N + \text{SDU}_N$

  The control (header) information added to the SDU to produce the PDU has all the necessary information for $\text{PDN}_N$ to be used as $\text{SDU}_{N+1}$ (and thus, be the payload now).

  Thus the PDU encapsulates the SDU and the control information.

• Peer processes

  Peer processes are those running on the same network layer on different devices that are communicating.

• SAP

  Any layer’s service can be accessed through its Service Access Points

• Ethernet operates on 10Mbps to 100Gpbs

• Fibre optic operates on 10Gbps to 100Gbps

• Link capacity is just bandwidth

• International Organisations

  • IEEE

    • Institute of Electrical and Electronics Engineers

    • Data link layer

    • Physical layer

  • IETF

    • Internet Engineering Task Force

    • Network layer

    • Transport layer

    • Request for comments (RFC)

  • W3C

    • World Wide Web consortium

    • Application layer

  • ISO

    • International Organisation of Standardisation

    • Open systems interconnection (OSI)

    • All layers

  • ITU

    • International Telecommunication Union

    • All layers

• IPC

  Inter-Process-Communication

  • Through the files (disk)

  • Through PIPE (not storing to an actual file, but rather passing chunks directly to next process in RAM itself)

  • FIFO channels are persistent named channels that are stored in the file system. This is similar to PIPE, except they allow communication between unrelated processes. Note that the actual data only goes through RAM, never through the disk.

  • Mailbox is a shared data structure where one process can write a message and another can read it, similar to the buffers you usually have in a producer-consumer problem.

  • Shared memory (RAM) is another easy way for IPC. This is a block of RAM that is in the address space of both the processes.

  • Message passing is what the mailbox DS allows.

• In the client-server app. arch. , the server is by-definition, always on and has a static IP address.

• P2P characteristics

  • no always-on server

  • self scalibility’

  • complex management

• Generic Requirements for application layer protocols

  Read that again. It’s the requirement, not the service. The requirements are in fact services provided by transport layer protocols.

  • data integrity (reliable data transfer)

  • timing (guarantees on delay)

  • throughput
    • Instantaneous Throughput insensitive apps are called “elastic”.

  • Securiy
    • There’s this thing called SSL that only exists for that one purpose.

• FTP (RFC 959)

  • The client first connects to the server on port 21.

  • The client is then authorised using username and password.

  • Just using port 21 TCP connection the client can navigate the filesystem already. This TCP connection is called the “TCP control connection” .

  • To receive a file, the server opens a second non-persistent TCP connection through port 20, called the “TCP data connection” .
    When the transmission is done, this connection is closed.

  • The server has to maintain the state for each connection (current directory, authentication, etc.)

  • In networking, when data and control share the same connection, it’s called in-band. So FTP control connection is “out-of-band” .

  • The client is made up of 3 parts :

    • Application interface (GUI or shell)

    • The Protocol Interpreter (PI) , which interprets the FTP commands coming from above and replies coming from the server’s PI.

    • The Data Transfer Process (DTP) which only handles data transfer.

  • The server process has 2 parts:

    • The Protocol Interpreter (PI) which interprets commands, makes changes in state (variables) and sends responses.

    • The Data Transfer Process (DTP) which handles data transfer

  • Although DTP is called “process”, it’s actually not a separate process in the OS sense, just in the logic sense.

  • FTP command are sent as ASCII text

  • FTP commands

    • USER <username>

    • PASS <password>
      If no password is needed, you may skip that field.

    • LIST [<directory>]
      lists file in current directory or one given

    • RETR <filename>
      Downloads a file

    • STOR <filename>
      Uploads a file

    • DELE <filename>
      Deletes a file

    • CWD <directory>
      Changes current working directory

    • MKD <directory>

    • RMD <directory>

    • PWD
      Prints working directory

    • CDUP

      Changes to parent directory.

    • QUIT

    • HELP [<command>]
      Shows help in general or for specific command.

  • FTP return codes

    • 331 Username Ok, password required

    • 125 data connection already open; transfer starting

    • 425 Can’t open data connection

    • 425 Error writing file

• Can you transfer executables via FTP ?

  Yes, you can.
  There are two transfer modes, ASCII mode, which is unsafe for executables and images since it converts line endings between systems (\r\n vs \n) , and the binary transfer mode which doesn’t do that.

  You can change the mode using the TYPE command. By default, it is ASCII. You can set it to binary using TYPE I (where I stands for “Image”)

• PTP and MTP are transfer protocols for Photos and Media.

• Since FTP transmits data in cleartext, it was removed from the FireFox browser on July 13, 2021

• FTPS

  To make FTP more secure, you can use SSL/TLS rather than simple TCP. This leads to what is called as the FTP-Secure protocol.

  It’s used by .NET

• SFTP

  Another method is to use SSH to do file transfer, rather than FTP. This leads to the SSH-File Transfer Protocol.

  Sometimes it’s also called the Secure File Transfer Protocol.

  Note that this is NOT just FTP over SSH, but a whole new protocol.

• TFTP

  The Trivial File Transfer Protocol is an extremely simple protocol that does no authentication, no encryption, no directory listing or navigation. It provides only read/write capability.

  This is used for embedded devices, network boost, routers, and other non-computer-like devices.

• Uniform Resource Locator (URL) is the address of an object

• Uniform Resource Identifier (URI) is just an identifier. It doesn’t locate the object.

• All URLs are URIs but not the opposite.

• HTTP is stateless
  Server maintains no info about client history (except cookies and stuff, but that’s just people extending it).

• HTTP methods

  • GET (was there in HTTP/0.9)

  • HEAD (HTTP/1.0)
    Just gets the status line and header

  • POST (1.0)
    Puts name,value pairs in body of request message

  • PUT (1.1)
    Uploads the object (data in message) to the given URL on server

  • OPTIONS (1.1)
    Get the information about what actions (methods) are available on a particular resource (URL). This info is put in the “Allow” header in the response message.

  • DELETE (1.1)
    Deletes the file with the specified URL

  • TRACE (1.1)
    It’s for debugging purposes. It lets the client see if any proxies or gateways are modifying the request.

  • CONNECT (1.1)
    This is used to create a network tunnel through a proxy to another server. Basically, the client sends the CONNECT request to the proxy with the host being the target server. The proxy than creates a connection to the target and forwards messages from client to the server, without looking at them.

  • PATCH (1.1)
    Partially updates an object, unlike PUT which replaces the full thing.

• HTTP response status and phrase

  • 200 Ok : request succeeded.

  • 301 Moved Permanently : File not at URL. New location is specified in the location header

  • 304 Not Modified : Response to conditional GET

  • 400 Bad Request : Parse error

  • 401 Unauthorised : Wrong or missing authentication

  • 404 Not Found : Nothing found on the URL.

• Idempotent, Safe, Cacheable

  Method	Type
  TRACE	Safe
  OPTIONS	Safe
  GET	Cacheable
  HEAD	Cacheable
  PUT	Idempotent
  DELETE	Idempotent
  POST	Not Idempotent
  PATCH	Not Idempotent
  CONNECT	Not Idempotent

  The reason TRACE and OPTIONS are safe but not cacheable is because it would be wasteful.

• URL length in HTTP message is 2048 characters.

• Since GET uses URL to pass variables, it has a limit on amount of variables it can pass. Meanwhile, POST uses the message body and has no limit.

• HTTP is stateless, i.e. the current request output doesn’t depend on past requests.

• HTTP is not sessionless. It does keep some information about the type and credentials of user in cookie files.

• Third party cookies are cookies set by other websites that are tracking your actions on the website you are currently on.

• “Second party cookies” are not a thing. Informally, it’s when a company shares its data with another party rather than have the other party track the users’ actions through third party cookies.

• Only ASCII characters are allowed in GET (since it’s encoded in URL), while even binary data is allowed in POST.

• GET should NOT be used for login. The recommended method is POST.

• Just as POST requests can’t be cached, neither can a POST response (page) be bookmarked.

• Uses of cookies

  • authorisation (login)

  • maintaining session state across logins (think, web e-mail and shopping carts)

  • Tracking (google does this). Helps them place ads.

  • Personalisation (meta does this)

• In guest mode, cookies are temporary and are deleted when you close the tab/session

• Head-of-Line (HOL) Issue.

  • in HTTP/1.1 pipelined requests, the objects would be arranged serially on the TCP connection. Now, if one TCP segment is lost for a particular object, the other objects too would have to be retrasmitted (assuming no buffering of out-of-order packets)

  • In HTTP/2.0 the objects are interleaved on the connection. So if there’s a packet drop, some data for each object has still arrived. Using SVD and other things, you can make web-pages still appear to have loaded.

  • In HTTP/3.0, rather than using TCP, we use QUIC, which doesn’t face this issue.
    HTTP/3.0 also allows UDP by the way…

• Conditional GET contribution to average page load time

  The textbook uses a model of web-caching where conditional GET doesn’t happen, when solving problems even though they detail the process differently. This is because in real life, the conditional GET is only done periodically.

• For a conditional GET, the responses can be:

  • 304 Not Modified status and no data

  • 200 OK and the object requested.

• HTTP 0.9

  • No headers

  • GET was the only method

  • No status codes

  • No “version” field (obv)

• HTTP 1.0

  • HEAD and POST methods

  • headers

  • version

  • status code

  • more content types

• HTTP 1.1

  • remaining 6 methods (PATCH,CONNECT,TRACE,OPTIONS,PUT,DELETE)

  • Persistent and Pipelined connections

  • Longer lived connections

  • Chunked transfers

• SPDY

  • Server push

  • Binary Framing layer

• HTTP 2.0

  • a solution to HOL blocking

• HTTP 3.0

  • Ditched TCP to go for QUIC. This is a transport layer protocol which runs over UDP .. yes, a layer 3 proto. over another layer 3 proto. Well, it is what it is.

  • Enhanced privacy and improved performance

• SMTP

  • Simple Mail Transfer Protocol

  • First RTT for TCP connection

  • In Second RTT, server states it’s ready with status code 220

  • In Third RTT, the client sends a HELO or EHLO and gets a reply from the server (expected is “250 Hello…”)

  • Finally, the client asserts it’s going to send mails using MAIL-FROM and RCPT-TO and DATA. When given an ok signal from the server, it sends the mail and ends with a “.” .

  • Uses 7 bit ASCII

  • Persistent TCP connections

  • port 25 , 587 or 2525

  • Mail syntax is headers (”From”,”To”,”Subject”,”Date”,etc.), a blank line, data and “.” .

  • push protocol

  • Mail server rotates mails and sends a response to the browser it was unable to send after a timeout.

• IMAP

  • Internet Message Access Protocol

  • 7 bit ASCII

  • Folder structure

  • Keeps the mail on the server

• DNS

  • Domain Name System (the system/service and the protocol)

  • distributed database

  • CNAME, NS and MX type RRs map names to names. Only A and AAAA map names to IP address

  • The logical hostname in a FQDN is the first component.

  • 13 root name server companies

    • 10 in USA

    • 1 in Netherlands

    • 1 in Sweden

    • 1 in Japan (this is where RR for in TLD is stored)

  • The actual number of root name servers are over 1000

  • NIXI, an indian organisation manages 54 root name servers, located in multiple cities.

  • Network Solutions maintains the .com TLD servers

  • Educause maintains .edu TLD servers

  • All local servers know the root servers. (Their IP addresses are stored in a local configuration file).

  • DNS uses TCP as a fallback if message length is too big

  • To set up a new hostname on DNS, you need to register it at a DNS registrar

  • registery.in for example, is a DNS registrar.

  • There are more than 1000 registrars worldwide.

• DNS syntax

  

  • 6 header fields, each of 2 byte:

    • id

    • flags

    • no. of questions

    • no. of asnwers

    • no. of authoritative RRs

    • no. of additional RRs

  • Question section has (name,type) tuples.

  • Other 3 sections have full RRs.

  • Full domain name must be strictly less than 256 characters

  • Each component of the domain name must be strictly less than 64 characters

  • Only alphabets, numbers, and hyphens are allowed in the components

  • DNS is case insensitive.

• TTL in DNS

  This is NOT in the TTL for IP datagrams. Instead, it’s the time for which a RR can be cached by a server that isn’t authoritative for it.

  This is done to avoid out-of-date address translation.

• Quantum Networks (1.25)
  • Instead of a classical stack, there’s a quantum stack.
  • IP layer, but using quantum computing
  • Create a routing algorithm
  • Implement on simulators
  • Reference paper. Implement the result and then your own.

• Quantum BGP
  • Paper is there. Implement on simulator
  • Validation and benchmarking
  • IP layer

• Understanding host network stack.

• SDN based routing

• Open source blitzping
  • traceroute like thing
  • uses dpkd rather than native socket API

• IPv6 Routers using P4 programming language (5) (1.8)
  • Simulation tools like MiniNet

• Distributed Network File System
  • Caching on client side
  • Already done…

• Network telementary
  • Monitor routers in real time
  • SNMP

• Network congestion control simulator
  • Educational tool

• DNS query and resolving visualiser
  • Educational tool

• Pre-process bandwidth tracker using eBPF
  • real time
  • Learn eBPF

• Packet drop logger using eBPF

• Southbound communication (SDN) using UDP rather than TCP

• Securing southbound communication using Post-Quantum cryptography algorithms (6) (1.8)

• MCP server and AI

• MCP based protocol (DASH, SFTP, etc.) selection (2.15)

• Multi path TCP and QUIC metric comparison

5G stuff …

• RDT is

  • (packet) loss free

  • error (corruption) free

  • in-order

• Silly Window Syndrome : The receiver advertises a small window size and the sender send segments of that (less than MSS). This causes the TCP/IP headers to dominate, wasting bandwidth.

• Clark’s Solution (ACK with-holding) : The receiver should only ACK when the receiver window size is more than a fixed amount (1 MSS or the half the buffer size)

• Tinygram syndrome : The application layer on the sender’s side only generates data in very small segments (think, an interactive terminal). This again, causes the TCP/IP headers to dominate.

• Neagle’s solution : The sender should buffer data that comes from the application layer into the TCP buffer till a certain size is reached.

• UDP data format

  • src port (16 bits)

  • dest port (16 bits)

  • length (16 bits)

  • checksum (16 bits)

• Wrap-around binary addition

  Consider the 4 bit numbers 1101 and 1010 . Adding these two gives sum of 0111 and c-out of 1; basically 10111 . Now, we can wrap-around the c-out back to the units place giving us 0111 + 1 = 1000 as the wrap-around sum. Denote by $$$\boxplus$ the wrap-around sum. Then, for $A = (1101)$ and $B = (1010)$ , you have $A \boxplus B = (1000)$ .

• IP Pseudo-header

  • 32 bit srcIP

  • 32 bit destIP

  • 16 bit Datagram Length

  • 8 bit Upper layer Protocol code

  • 8 bit of padding

• Checksum

  • Create the UDP segment, with UDP checksum set to 0

  • Add the IP pseudo-header to the segment

  • chunk into 16 bit words

  • Wrap-around binary add the 16-bit words

  • Take one’s complement of the sum.

• TCP segment structure

  • ports (32 bits)

    • 16 bit src port

    • 16 bit dest port

  • 32 bit seq. no.

  • 32 bit ack. no

  • 4 bit header length (number of 32 bit words in the full TCP header)

  • 4 bit reserved

  • Flags (8 bits)

    • CWR

    • ECN/ECE

    • URG

    • ACK

    • PSH

    • RST

    • SYN

    • FIN

  • 16 bit Recieve Window Size

  • 16 bit Urgent Pointer

  • 16 bit Checksum

• Problem with 2-way handshake

  • server won’t have a good estimate for RTO

  • SYN packet flooding is easy for the client since client doesn’t need to allocate resources or wait.

  • RFC 793 “Duplicate packets from previous connection” (Fals/ Half-open connections)

    Suppose the client retransmits the SYN one time, giving us two SYN packets on the wire. The first one reachers the server and the server allocates resources. Now, when the second one reachers the server; in the eyes of the server there are two things that could’ve happended :

    • The client didn’t get the first ACK back and retransmitted (the actual reason)

    • The client closed the connection and after some time (MSL), started a new connection.

    Note that the server will have this confusion regardless of how far apart the two SYNs are, since the RTO can grow arbitrarily large; and there can be multiple retransmissions 1,2,3…n for the SYN; with only the first and last (nth) SYN reaching the server.

• TCP client connection closing

  • FIN_WAIT_1 : FIN is sent and we will wait RTO for ACK. We have also deleted the send-buffer. So, we can only recieve now.

  • FIN_WAIT_2 : ACK from server is recieved. Now, we must wait for server to finish and send the FIN.

  • TIME_WAIT : FIN is recieved and ACK is sent back. We will keep sending back ACKs for any FINs we recieve for the next 2*MSL time.

  • CLOSE : After 2*MSL , we have deleted the recieve buffer too.

• TCP server connection closing

  • CLOSE_WAIT :
    • FIN arrived from client
    • ACK returned in response.
    • closed the reciever buffer.

  • LAST_ACK :
    • Send buffer closed
    • FIN is sent

  • CLOSED :
    • ACK is recieved.

• 3 D-ACK

  When sender recieves 3 dup-ACKs; thus, in total 4 ACKs with same acknowledgement number, then it will retransmit exactly one segment and stop the timer.

  The number “3” is chosen mostly based on ad-hoc reasoning and data analysis.

  D-ACK retransmit suffers from un-ordering of segments, in which case the later segments that arrive too early are either discarded or buffered, and duplicate ACKs are sent in return.

  The higher the threshold for D-ACK count, the more is small un-ordering allowed.

• Silly Window Syndrome

  When the reciever has less than 1MSS of window left and it sends ACK also asking to sent the rwnd to that size, the sender will start sending data with segments of that size (< 1MSS). The same amount of data will be consumed by the application and the cycle will continue.

  This is problematic because the TCP/IP headers dominate the actual data on wire; thus decreasing the goodput.

  A partial solution is ACK witholding

• Tinygram Syndrome

  Here the sender itself is sending segments with very little data (tinygrams). This is not because the reciever has a small buffer space left at any moment, but because the appication at the sender is sending data as soon as it is produced.

  For example, remote terminals sending 1B of payload every segment.

  This again, leader to the stream being dominated by headers. To solve this, ACK witholding at the reciever’s end won’t work (it will cause error on sender’s side).

  Neagle’s solution : Instead, the sender should buffer the data till it becomes enough to fill 1 MSS.

  This is actually implemented in TCP and can be disabled using TCP-NODELAY option.

• TCP initial cwnd value

  MSS (B)	cwnd (MSS)
  (0,1095]	4
  (1095,2190]	3
  (2190,infinity)	2

• Update ssthresh on loss-event as max(cwnd/2,2*MSS)

• Slow start will never go beyond ssthresh even if this is happening in the middle of a transmission round.

• TCP Tahoe loss event

  • ssthresh = max(cwnd/2,2)

  • cwnd = 1

  Note that both ssthresh and cwnd are in MSS units.

• TCP Reno loss event

  • ssthresh = max(cwnd,2)

  • if timeout:
    • cwnd = 1

  • elif 3 D-ACK :
    • cwnd = ssthresh

• TCP new Reno loss event

  • ssthresh = max(cwnd,2)

  • if timeout:
    • cwnd = 1

  • elif 3 D-ACK :
    • cwnd = ssthresh + 3

• TCP evolution

  • Tahoe : Only SS and CA

  • TCP Reno :

    • Fast retransmit and recovery

    • header compression (omit some TCP header feilds if ACKs are recieved regularly)

    • delayed ACK (ACK on alternate segments and buffer one segment)

  • TCP NewReno

    • Better Fast-recovery (the +3 thing)

    • TCP option “SACK” (buffer arbitrary number of segments at reciever)

  • TCP CUBIC

    Faster congestion response in high speed networks

    

    • $W_\text{max}$ is the window size at which congestion was last noticed.

    • Define $K$ as the time for which, after a loss the rate is to increase, eventually reaching $W_\text{max}$

    • The window $W$ grows as $W(t) = W_\text{max}(1-\frac{1}{2}(1-\frac{t}{K})^3)$ .

  • TCP Vegas

    • Delay based

    • $\text{RTT}_\text{min}$ is the minimum measured RTT.
      Ideally, this should be the RTT for the congested path.

    • The uncongested throughput is thus $\text{cwnd}/\text{RTT}_\text{min}$

    • if the measured throughput is “very close” to un-congested throughput, then increase cwnd linearly .

    • if measured throughput is lower, decrease cwnd linearly

    • This method maximises throughput

    • Doing the same thing but with delays instead of rates maximised good-put rather than throughput.

    • This is a very submissive algorithm. Aggression by other flows will cause it to decrease the cwnd linearly, thereby giving the competitors even more breathing space, which no initial exponential increase phase for re-calibration.

  • TCP BBR

    • Rate based

    • Estimates Bandwidth-Delay-Product using both RTT measurement (delay) and loss events

    • Keeps the sending rate (not just cwnd ) equal to the rate of the bottleneck link, thus avoiding bursts and queuing.

    • While loss events are used too, their effect on the sending rate is reduced, making TCP BBR aggressive since it doesn’t care about failures (losses) that much and doesn’t give the competitor flows any breathing space.