IP protocol — RFC study notes.

Here’s the original. (Recommended for the studious).

Scope limits:

There are no mechanisms to augment end-to-end data
reliability, flow control, sequencing, or other services commonly
found in host-to-host protocols.

Basic Functions:
1. Addressing:
a, Routing: Based on the addresses carried in the header, the datagrams are sent to destinations.
Which path they take is decided by routing.

2. Fragmentation:
The IP layer/module fragments the given data to it into datagrams for transmission through “small packet networks”.

Each Internet Datagram is an independant entity.
4 Mechanisms:
1. Type of Service:
Quality of service, as codified into parameter values defined by the layers above, and implemented/honoured by the gateways, to choose the transmission parameters.
2. Time to live:
Self-destruct time-limit for each datagram. Cool like self-destruct messages in Spy movies(mission impossible)
3. Options:
Used for control functions/commands
4. Header Checksum:
Like any other checksum, check to make sure the data transmitted is correct.

Addresses vs Names vs Routes:
address == Fixed length four octets
octet — eight bits.
Address starts with
1. Network Number
2. local address/rest field
# TODO: an example would help here.
types of local address:
a, highest order bit is zero, next 7 bits the network, last 24 the local address
b, high order two bits 10, next 14 bits the network, last 16 the local address
c, high order 3 bits 110, next 21 bits are the network, and last 8 the local address
Address Formats:

Address Formats:

High Order Bits Format Class
————— ——————————- —–
0 7 bits of net, 24 bits of host a
10 14 bits of net, 16 bits of host b
110 21 bits of net, 8 bits of host c
111 escape to extended addressing mode

— Used when a packet originates in a local net of higher packet size than the target local net
— packets can be flagged to never fragmented(but dropped if the case above happens)
— fragments have
identification field
offset field
more-fragments flag
Also have the same header as the original IP packet.

Forward datagrams between networks

| Internet Protocol & ICMP & GGP|
| |
+—————+ +—————+
| Local Net | | Local Net |
+—————+ +—————+

Gateway Protocols

Internet Header format:

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
|Version| IHL |Type of Service| Total Length |
| Identification |Flags| Fragment Offset |
| Time to Live | Protocol | Header Checksum |
| Source Address |
| Destination Address |
| Options | Padding |

Example Internet Datagram Header

version: 4 bits
IHL : 4 bits, length of the header in 32 bit words
Type of Service: 8 bits
So the choices boil down to low-delay, high-reliability and high-thoroughput.

Bits 0-2: Precedence.
Bit 3: 0 = Normal Delay, 1 = Low Delay.
Bits 4: 0 = Normal Throughput, 1 = High Throughput.
Bits 5: 0 = Normal Relibility, 1 = High Relibility.
Bit 6-7: Reserved for Future Use.

Total Length: 16 bits
— length of the datagram measured in octets, Max 65535 octets.
— hosts are recommended to send > 576 octets.(576 heuristically arrive number, probably higher nowadays??)
Identification: 16 bits
— identification for fragmentation and re-assembling.
Flags: 3 bits

Bit 0: reserved, must be zero
Bit 1: (DF) 0 = May Fragment, 1 = Don’t Fragment.
Bit 2: (MF) 0 = Last Fragment, 1 = More Fragments.

0 1 2
| | D | M |
| 0 | F | F |

Fragment Offset: 13 bits
Time to live: 8 bits
Protocol: 8 bits
— Next level protocol used
Header Checksum: 16 bits

The checksum field is the 16 bit one’s complement of the one’s
complement sum of all 16 bit words in the header. For purposes of
computing the checksum, the value of the checksum field is zero.

Source Address: 32 bits
Destination Address: 32 bits
Options: variable
— transmission of options is optional.
2 formats:
a, Single octet of option-type
b, option-type octet + option-length octet + option-data octets
option-type octet:
1 bit — copied flag( whether to copy this option to each of the fragments)
2 bits — option class

0 = control
1 = reserved for future use
2 = debugging and measurement
3 = reserved for future use

5 bits — option number
Defined internet options.

—– —— —— ———–
0 0 – End of Option list. This option occupies only
1 octet; it has no length octet.
0 1 – No Operation. This option occupies only 1
octet; it has no length octet.
0 2 11 Security. Used to carry Security,
Compartmentation, User Group (TCC), and
Handling Restriction Codes compatible with DOD
0 3 var. Loose Source Routing. Used to route the
internet datagram based on information
supplied by the source.
0 9 var. Strict Source Routing. Used to route the
internet datagram based on information
supplied by the source.
0 7 var. Record Route. Used to trace the route an
internet datagram takes.
0 8 4 Stream ID. Used to carry the stream
2 4 var. Internet Timestamp.

Each of these options then have more specifications about what they mean, and how they should work. That goes on for a couple of pages.
There are a couple more pages discussing some implementation requirements and some examples but this is as far a i go.

Urlshortener in python

I attempted this(url shortener) project as a kind of a dare. Over a lunch one day, atul casually commented that a url shortener,

would be a ten minute work for someone like you and a blog about it would make a nice fit for my site.

I was not sure it’s a 10 minute work, but sounded like a small fun project for weekend attempts.

It took more than half a day, for me to be content(not happy, but just content) with the resulting work.

Nevertheless, it was time well spent. Here’s the link to the actual project.<a href=”https://github.com/emofeedback/urlshortener”&gt;


Few clarifications about some choices(should i call it software engineering??):

  1. Redis because it’s extremely efficient, stays in RAM, and has some unconfirmed reports of being used to power china’s internal twitter clone.
  2. RAM based data base means lower latency, as opposed to a disk+ cache based database, but needs higher RAM.
  3. Used 5 chars, because, well the internet is big, and thought it’s a good number to cover most unique urls.(especially, when combined with the 78 chars allowed for url, i.e: 5^78) Thanks to a colleague’s suggestion for the idea, i was thinking about hashing/random before his suggestion.
  4.  A hash map of shortened url-> original url and original url -> shortened url was kinda against my idea. I still keep thinking this is too much memory, we should find a different way. I think if I take away the use-case of already shortened url, being submitted for new shortening, should return, I can eliminate the original url -> shortened url hash map.
  1. To check if a new original url has already been shortened, the hyperloglog comes to the rescue. Just pass it through the HLL algorithm and see if it returns True and False.
  2. From the UI point, well i just put up a minimal html form to take a original url and return a json.
  3. Yet to do, add a proper fabric script to setup virtualenv, python packages, redis install and nginx config and restart nginx.

You can see it live here.