Network Layer Overview
Names of data units:
- Application: message
- Transport: segment
- Network: datagram
- Link: frame
Responsibilities of layers:
- Network layer: responsible for finding a route from A to B
- Transport layer: responsible for transporting data from A to be reliably or easily
- Application layer: responsible for sharing data
Layering: each layer takes data from above, adds header information then passes the new data unit to the layer before.
Possible services of a general network layer:
- Guaranteed delivery (with/without bounded delay)
- In-order delivery
- Guaranteed minimal bandwidth
- Guaranteed maximum jitter
- Jitter: gap between two consecutive messages
The internet network layer, IPv4 guarantees none of these.
Routing Overview
Routing is a network-wide process that determines the end-to-end paths packets take from source to destination.
The network needs to work out the path from the sending to receiving router automatically in an dynamic environment.
A router uses its routing table to forward a packet to some output link.
The router’s switch fabric - the physical architecture of the router, varies. Some implementations put the network interfaces/line cards close to the CPU to decrease processing times. The cross bar architecture is used to more quickly forward packets to outgoing interfaces.
Hierarchical Overview
There are inter-AS and intra-AS routing algorithms, where AS stands for an autonomous system.
Each ISP is an AS, and some corporations and universities are also ASs.
Each AS is a set of routers and networks managed by a single organization. The routers exchange information via a common routing protocol - the intra routing protocol.
The only inter-AS routing protocol is that is used is BGP. The RIP and OSFP protocols are the two main intra-AS routing protocols. All three are load-insensitive.
There are three types of AS:
- Stub AS
- Has only one connection to another AS
- Like a leaf node
- Multi-homed AS
- Has more than one connection to other ASs, but does not allow traffic to path through
- e.g. university network will not be doing forwarding
- Transit AS
- Has more than one AS and allows traffic to path through
- Run by ISPs
Forwarding vs Routing
Forwarding and routing are two independent processes.
Routing determines the path to take:
- Is not done packet-per-packet
- Is non-real time: up to two minutes of latency
- Requires communication between routers to jointly create forwarding tables
Forwarding transfers packets hop-by-hop:
- It determines which outgoing link to use on a packet-by-packet basis
- Is done in real time, possibly in hardware
The forwarding table:
- Maps a destination address to an interface
- Results from either the execution of the routing protocol or is static and preconfigured
- Is consulted for every packet
- Changes on relatively large timescales (e.g. topology or load changes)
Classification of Routing Algorithms
Routing algorithms solves a routing problem with ideal assumptions. Routing protocols embeds a routing algorithm in a real network environment; it operates in a distributed environment and can work around failure cases.
Classifications
Static/dynamic
Static algorithms change very slowly over time, mostly due to human intervention.
Dynamic algorithms re-compute routes in response to topology or traffic changes. The computation may occur periodically or in response to changes.
Global/Decentralized
Global algorithms assumes each node has global knowledge/state information on the network.
Decentralized algorithms assume no node has complete state information about the network and exchange information with their neighbors.
Load-sensitive/-insensitive
Load-sensitive algorithms assume link costs vary dynamically depending on the level of congestion in the link.
Internet routing protocols such as RIP, OSPF and BGP are load-insensitive and assign a static cost to each link.