Network Layer Protocols

Building Link State Packets

• Link state packets contain:

  • Identity of the sender

  • Sequence number

  • Age of the packet (time to live)

  • List of neighbors

    • For each neighbor, the delay (or other metric) is given

• Problem: When to build the link state packets?

  • Periodically, upon changes, on demand …

Distributing Link State Packets

• Important part of the algorithm:

  • When a router receives the packet, it updates the routing tables.

  • Not all the routers receive update at the same time, leading to possible inconsistencies.

• Packets are distributed via flooding.

  • Flooding overhead is minimized via use of sequence numbers; only new updates are forwarded.

• Possible problems:

  • Sequence number wrap-around

    • Use a 32-bit sequence number; with one link state packet per second, wraparound occurs in 137 years!

  • Router crashes

  • Sequence number corrupted

  • Such problems call for a robust solution, which justifies flooding, even if it makes unnecessary repetitions.

• Endow each packet with an age field in the header.

  • The age value is decremented every second.

  • When the age hits 0, the packet is discarded, preventing infinite looping.

  • Age is also decremented during flooding by each router.

    • Ensures that each packet will be dropped without living indefinitely.

• Link state packets are acknowledged.

Computing the New Routes

• Once a router has received a full set of link state packets, it builds a local representation of the topology.

• Dijkstra algorithm is run locally to compute shortest paths.

• The required local storage for a network with $n$ nodes and average node degree $k$ (=average number of neighbors) is $O(kn)$.

  • Not so scalable for very large networks; hierarchical routing may be used (see later).

Use of Link State Routing

• OSPF (Open Shortest Path First) is used in the Internet (discussed later).

• IS-IS (Intermediate-System Intermediate-System) was adopted for the connectionless network layer protocol of ISO.

  • Variations are in use in some parts of the Internet backbone (old NSFNET) and in some digital cellular systems.

• OSPF adopted many ideas from IS-IS, so they became quite similar.

• Among these protocols, we discuss OSPF in details, as that is the most commonly used link state routing protocol (see details later).

Hierarchical Routing

• If the size (number of nodes) of the network grows, then:

  • Routing tables grow proportionally.

  • Time needed for route update grows.

  • Bandwidth needed for routing info exchange grows.

• A possible solution: Hierarchical routing

  • Has been used in the telephone network for a long time.

• Routers are divided into regions.

• Routing is performed non-hierarchically within the region.

• A router knows nothing about the routers in other regions (only knows how to reach the other region, but not the specific routers within it).

• For very big networks a hierarchy with more than 2 levels may be needed:

  • Regions may be grouped into clusters

  • Clusters into zones

  • Zones into groups

  • Groups into multi-groups

  • Multi-groups into supergroups

  • Supergroups into hypergroups… etc.

• Hierarchical routing example Naming convention in the example: 1A is router A in region 1, 5B is router B in region 5, etc.

• In the hierarchical table for 1A the other regions are viewed as single nodes.

Hierarchical Routing Drawbacks

• Hierarchical routing imposes increased path length.

  • Example: best route from 1A to 5C would be through Region 2, but all traffic goes from R1 to R5 through R3, as that is best for most destinations in R5.

• Determining how many levels a hierarchy should have is non-trivial.

  • More levels: smaller routing tables, but higher loss in path optimality.

  • Network planning is more difficult with hierarchical routing.

• Kamoun and Kleinrock (1979) proved in a theoretical model that $\log n$ is the optimal number of levels for an $n$-node network.

Broadcast Routing

• Broadcasting: sending a packet from a source node to all other nodes in the network.

• Simple solution: route the packet to each single node individually

  • Wastes bandwidth

  • Requires the source to know all destinations.

• Another candidate: Flooding

  • Generates too many duplicate packets, consumes too much bandwidth.

• Other broadcasting algorithms (see subsequent slides):

  • Multi-destination routing

  • Spanning-tree based routing

  • Reverse path forwarding

Multi-destination Routing

• Each packet contains each intended destination or a bitmap of them.

• When a router receives a packet, it decides the proper output lines.

• A copy of the packet is generated and sent out in all the selected lines

  • Destinations are modified accordingly

    • Destination set is partitioned among output lines: only those destinations are kept in a group that need to go through that output line.

    • Group sizes eventually reduce to 1, and become normal packets.

Spanning-Tree Based Broadcasting

• A spanning tree is a subset of the links of the subnet that contains all nodes but has no loop.

• If a router knows which outgoing lines belong to the spanning tree, it sends the packet on those.

• Optimal bandwidth usage: only used what is needed.

• Problem: A node must know which of its lines are in the tree

  • Available info with link state routing, but not with DVR

Reverse Path Forwarding

• A node checks if the packet it received came from the line used by this node for sending packets to the source (preferred direction to the source).

  • If so, the packet is sent out on all the lines (except the one it came from).

  • If not, the packet is discarded (as a duplicate).

• Advantages

  • Reasonably efficient and easy to implement

  • Does not require a router to know it is on a spanning tree. It only needs to know the next hop to a destination, which is available in the routing table. This already determines the sink tree.

  • Does not have the overhead of a destination list or bitmap in each broadcast packet

  • Does not require an extra mechanism to stop the forwarding process (as in flooding).

    • Why?

    • Because when a leaf of the tree is reached and it forwards to a neighbor, the packet will not come from the preferred direction to the neighbor (=along the tree), so this neighbor will not forward the packet anymore  no extra mechanism needed to stop forwarding.

The Network Layer, Principles of Internet Design

• Top ten principles for the design of a successful protocol From IETF [Internet Engineering Task Force]

• Generally: Make sure it works Involves testing, validation
  The 10 principles:

  1. Keep it simple: Occam’s razor (Law of Parsimony, 14th century): when in doubt, take the simplest choice.

  2. Make clear choices: Choose one way of doing things, be clear

  3. Exploit modularity: The layering concept

  4. Expect heterogeneity: Different hardware, software, technology

  5. Avoid static (rigid) options and parameters: Be flexible, negotiable

  6. Look for a good design, not for a perfect one: Leave weird cases out, rather than overcomplicating

  7. Be strict when sending, tolerant when receiving: Always comply, but be able to deal with those who don’t

  8. Think about scalability: Solutions should be able to accommodate future growth

  9. Consider performance and cost: Poor performance or outrageous cost = useless solution

The Internet Network Layer

• At the NL the Internet is a collection of interconnected subnets called Autonomous Systems (AS)

• There is a backbone of high-bandwidth lines and fast routers

  • Regional networks, attached to the backbone

  • LANs of companies, institutions, universities, ISPs etc., attached to the regional networks

• The Internet is an interconnected collection of many networks

• Overall “glue”: Internet Protocol (IP)

  • Created with internetworking in mind

  • Provides best effort way to transport datagrams from source to destination

    • Independent of where the machines are

  • Best effort = no guaranteed QoS (Quality of Service)

• Packets can be up to 64Kbytes

  • Usually 1500 bytes, fits the Ethernet frame
    Packets are transmitted through the Internet

• Possibly fragmented

  • The NL puts the packets back together (if fragmented) at the destination and passes it up to the Transport Layer

  • A packet can traverse many networks

The IP Protocol

• IP datagram = Header + Data

• Header = 20-bytes fixed part + variable-length part (for options)

• Header is transmitted from left to right

  • The high-order bit of the version field goes first

• The IPv4 packet header

  • IPv4 = version 4 of IP. For a long time, it has been the most commonly used version. Now IPv6 is rapidly being deployed, we discuss it later.

Fields of the IP Header

• Version (4 bits)

  • Specifies which version of the IP protocol the datagram belongs to

  • Makes possible to have long transition time between versions (co-existence)

• IHL (4 bits) tells how long the header is (IP Header Length)

  • In number of 32-bit words (a row in the figure)

  • Minimum 5 (no options), max 15 words

    • header can be at most $15 \times 4 = 60$ bytes

• Type of service (6 bits)

  • Distinguishes between different classes of services = various combinations of reliability and speed

  • Made up of a three-bit precedence field and three flags, D, T and R

    • Precedence, from 0 to 7, is a priority

    • Flags D,T,R indicate what the host cares about

      • Delay, Throughput, Reliability

  • In practice the Type of Service field is often ignored by routers

• Total length field (16 bits)

  • Includes everything in the datagram (header+data)

  • Max length is 65,535 bytes

• Identification field (16 bits)

  • Allows the destination to associate a fragment with a packet

  • All fragments of a packet contain the same identification value

• One unused bit

• Two one-bit fields

  • DF = Don’t fragment

    • Orders the routers not to fragment the datagram

  • MF = More Fragments to come

    • All fragments of a datagram have this field set, except the last one

• Fragment offset (13 bits)

  • Tells where in the current datagram this fragment begins, measured in units of 8 bytes

  • Any datagram can have at most 8192 fragments

• Time to Live (8 bits)

  • Counter, used to limit the packet lifetime

  • Time is counted in seconds for a maximum of 255 seconds

  • In practice it often just counts hops

• Protocol (8 bits)

  • Tells which transport process to give this datagram to

  • Possibilities: UDP, TCP, or some other (less frequently used) protocols

  • Numbering of these protocols is uniform across the Internet (managed by Internet Assigned Numbers Authority [IANA] www.iana.org)

• Header checksum (16 bits)

  • Verifies the header only

  • Must be recomputed at each hop.

    • Why? Because the Time to Live field changes in each hop!

• Source and destination addresses (32 bits each)

  • Network and host number

• Options field (variable length, max 40 bytes)

  • Was designed to provide for future features or tryouts

  • Variable length

  • Begins with one-byte code to identify the option

  • Padded out to a multiple of 4 bytes

  • Originally, there were 5 possible options

IP Options

• Some of the IP options

IP Addresses

• Every host or router on the Internet has a unique address

• It encodes network number and host number

  • 2-level hierarchy

• All IP (version 4) addresses are 32 bits long

  • Used for both source and destination fields

• Note: The IP address actually refers to a network interface, not to a host

  • If a host is on two networks, it has two different addresses (but this is rare, except for routers)

Dotted Decimal Notation

• IP addresses are written in dotted decimal notation

• Each of the 4 bytes is written as a number from 0 to 255

  • E.g.: 192.41.6.20

  • Lowest: 0.0.0.0, Highest: 255.255.255.255

Classful Addressing

• Original addressing scheme in the Internet

• Five categories of addresses

• No longer used but still commonly referred to

• Classes are named A to E. They are identified with the first few bits:

  • A= 0, B= 10, C= 110, D= 1110, E= 1111

• Classes A to C allow for

  • A: 128 networks with 16 millions hosts each

  • B: 16,384 networks with up to 64K hosts each

  • C: 2 million networks with 256 hosts

• Multicast is allowed

• Class E is reserved for future use

• Addresses are managed in a centralized way

  • ICANN: Internet Corporation for Assigned Names and Numbers

Special IP Addresses

• “This host” is used at booting.

• Loopback packets are not actually sent, they are only processed locally as received packets, for testing.

CIDR: Classless InterDomain Routing

• Problem: The Internet is running out of IP addresses

  • The 100,000th network was connected already in 1996

• Although 32 bits provides over 2 billion addresses, the class mechanism wastes many addresses

• Classless addressing provides a little more room for addressing

• Classes are no longer considered, and addresses are assigned in variable-sized blocks

• However, this complicates the way to forward a packet

  • Old fashioned forwarding considered classes

• Defined in RFC 1519.

• The router stores triples: (IP address, subnet mask, outgoing line)

• Each network is represented in the router by a base IP address and a subnet mask (that tells which part of the address is the network part).

  • Example: 194.24.0.0/21 -> the leftmost 21 bits represent the network

• When a packet arrives, the router searches the longest network match between its destination address and the base address of each network in the table.

  • Network match means that only the network part is considered, marked by the mask.

  • If there is no network match, the packet is forwarded to a default router.