The Network Layer

Note on 22 Jul 2002
Properties and Services

• The network layer normally offers one of the following services to the transport layer
  • Connection-oriented
  • Connectionless
• Network layers are designed with the following goals in mind
  • To provide services independent of subnet technology
  • To shield the transport layer from the number, type & topology of the subnets present
  • To use a uniform addressing scheme across both LAN & WAN

Virtual Circuits

• Used in connection oriented services
• Whenever two machines wish to communicate - a route from source to receiver is setup and remembered
• Advantages
  • easy congestion control
  • quick to parse subsequent packets
• Disadvantages
  • setup time
  • vulnerable to crashes

Datagrams

• Used in connectionless oriented services
• Everytime a packet is sent out, a new route maybe chosen
• Advantages
  • robust
  • no initial setup time
• Disadvantages
  • congestion is less easy to control
  • determining route of packet is more complex

Routing

• One of the main function of the network layer is routing packets from source to destination
• Routing is done using datagram on VCs
• Routing algorithm must have the properties of
  • correctness
  • simplicity
  • robustness
  • stability
  • fairness
  • optimality
• Routing algorithm can also be classed as
  • Nonadaptive
  • Adaptive

Shortest path Routing

• All hosts/routers must be known beforehand
• At network initialisation, calculate for each node, the shortest distance between it and every other node
• Distance is calculated in terms of weighted function of distance, bandwidth average traffic, communication cost, mean queue length, measured delay and other relevant factors
• Advantages
  fast
  simple
• Disadvantages
  • finding the shortesst path is NP problem
  • storing paths takes up memory

Flooding

• Send packets out on all lines, except the one it was received on
• Selective flooding variant - send packets out on all lines that are going in roughly the right direction
• Care needs to be taken to avoid infinite loops
  • use a hop counter
  • keep a list of seen packets from the source router
• Advantages
  • robust
  • easy to implement
• Disadvantages
  • Eats bandwidth

Flow-Based Routing

• Routes packets according to load of network
• In order to work, need to know
  • details of traffic flow
  • details of line capacity
  • subnet topology
  • a possible routing algorithm
• From this we can calculate
  • the traffic at any point in the subnet
  • the load at any point in the subnet
  • the shortest path through the subnet
• We can use flow based routing to compute routing algorithms and choose best one
• Advantages
  • efficient
• Disadvantages
  • complex
  • only works if the data flow is stable & predictable

Distance Vector Routing

• Early internet dynamic routing algorithm
• Each router maintains a routing table
• Once every T msec, these tables are sent to all the routers neighbours
• Updating tables
  • new tables come in from X
  • if we know that it takes m msec to get to X, we can work out the distance, from current router, to any route from X
  • do this for all tables and update routing table with shortest possible route

Distance Vector Routing count to infinity problem

• Good newa converges quickly - bad news doesn't
• Many adhoc solutions have been developed, most common is "split horizon hack" in which the distance to X is not reported on the line out to X
• None of these ad-hoc solutions are completely successful

Link State Routing

• Current internet routing algorithm, variants are widely used on other networks
• Dynamic variant of Shortest Path Routing
• 5 key stages
  • find out about neighbour & learn their network address
  • Measure the delay/cost to each neighbour
  • Construct a packet containing information in 2
  • Send this packet to all other routers
  • Compute the shortest path to every other router

Link State Routing - finding & measuring

• All routers have unique name
• Finding other routers
  • Send HELLO packet on all outgoing lines
  • On receipt of HELLO packet, send back id
• Measuring distance/cost to other routers
  • Send ECHO packet to all neighbours
  • Neighbours immediately send packet back
  • Time trip & divide result by 2

Link State Routing - constructing & sending a packet

• Packets can be sent periodically or when an event happens
• Packets are flood routed
• Every routing package is acknowledge
• Sequence numbers are used to ensure that obsolete information is ignored
• Aging is used to handle problems with corrupted sequence numbers

Link State Routing - Computing new routes

• Use same algorithm as Shortest path Routing to calculate new routing table

Hierarchical Routing

• Number of routers on the internet is large - keeping full routing tables is infeasible
• Solution is to impose hierarchy on routing
• Special routers (known as gateways) know topology of local subnet & id of other gateways
• Multiple levels allow reduction in size of routing tables, but at cost of efficiency

Congestion Control

• Congestion occurs for 2 main reasons
  • slow router
  • data from large bandwidth line(s) going to small bandwidth line
• Congestion is different from flow control - congestion is global property, flow control is point to point issue

Principles of congestion control

• Two main types of congestion control open & closed
• Open loop - try to prevent congestion occurring in the first place with good design
• Closed loop - use a feedback loop to control congestion
  • Monitor system to detect when & where congestion occurs
  • Pass information to places where action can be taken
  • Adjust system to correct problem

Leaky Bucket Algorithm

• Open loop congestion control
• Essentially a large buffer that smoothes out flow
• 2 main variants - packet and byte

Token Bucket Algorithm

• Similar to leaky bucket, but tokens are stored in bucket
• 1 token allows 1 packet to be transmitted
• Therefore idle machines can store up permission to send bursts of traffic
• Also get packet and byte variants
• Common to put leaky bucket after token bucket

Admission control

• Basic closed loop technique for VCs
• Very simple and commonly implemented
• If congestion occurs, do not allow anymore VCs to be setup until problem goes away

Choke Packets

• Each router monitors utilisation of output line
  U_new=au_old+(1-a)f
  where u=utilisation, a=aging constant, f=instanteous line utilisation (either 1 or 0)
• When u exceeds some threshold, the output line enters a warning phase
• Each newly arrived packet is checked to see if output line is in warning phase - if so
  • choke packet is send back to sender containing destination of packet
  • choke bit is turned on in packet (prevent other choke packets being sent further upstream)
• When a source receives a choke packet it is required to reduce the traffic sent to X by a specified amount
• Source then ignores other choke packets about X for a given time interval
• Source then listens for other choke packets - if it receives them it reduces the flow even more
• If no more choke packets come in, sender starts to increase flow again

Fair Queuing

• Choke packets depend on sender being well mannered
• One solution to get round this problem is to maintain a buffer for each sender, and 1 packet from each buffer in turn
• A variant for use with multiple sized packets is to send each packet in order of increasing size
• Another common variant is weighted fair queuing, where priority machines (e.g. servers) are allowed to send 2 bytes for every one of the other machines

Internet control Protocols

• IP is used for data transfer - other protocols exist in the network layer to help manage the internet
• ICMP (Internet Control Message Protocol)
  • Used by routers to communicate and test the internet
• ARP (Address Resolution Protocol)
  • Protocol for getting ethernet addresses for a given IP address
• RARP (Reverse Address Resolution Protocol)
  • Protocol for getting IP address for a given ethernet address
• OSPF (Open Shortest Path First)
  • Routing within networks/subnets
• BGP (Birder Gateway Protocol)
  • Routing between networks/subnets

The IP protocol header

• IPv4 packet format

 

 
IP addresses

• Special addresses
  • 0.0.0.0 - This Machine
  • 0.0.x.x - A machine on same class B network
  • 0.0.255.255 - broadcast on same class B network
  • x.x.x.255 - broadcast on other class C network
  • 127.0.0.1 - loopback

Goldilocks & the three bears

• Class A networks are too big for most people
• Class C networks are too small for many organisation
• Class B networks are just right, but only a limited amount of class B networks

Solutions

• Dynamic IP allocation
• CIDR (Classless InterDomain Routing)
• NAT
• Proxies

Dynamic IP address allocation

• Large upsurge in requirement for IP addresses has come from home use
• ISPs can only support a certain amount of users at a time - therefore maximum amount of IP addresses is much less than number of users
• How to tell user there IP address?
  • BOOTP
  • DHCP

BOOTP

• Bootstrap Protocol (RFCs 951 & 1532)
• Users machines broadcast a BOOTREQUEST packet to 255.255.255.255
• Server responds with BOOTREPLY packet which contains configuration details
• BOOTP is sent to server on port 67 and received by client on port 68 (why?)

DHCP

• Dynamic Host Configuration Protocol (RFCs 2131, 2132, 1534)
• Extension to BOOTP - reasonably interoperability
• Allows automated allocation of IP addresses from a pool
• Allows assignment of addresses for limited time periods
• Works of multiple subnets

CIDR

• Solution to lack of class B network was to get companies to use multiple class C
• Introduces problems with routing redundant information & large routing tables.
• Also early classes were allocated without regard to network topology
• Solution is to use Classes Inter-Domain Routing

NAT

• No longer allocate classes - allocate IP address ranges
• Allocate ranges wrt to network topology
• Introduce concept of netmask to determine what machines are in local network
• Network Address Translation (aka Masquerading)
• Servers have standard IP address - all others have private IP address (RFC 1918)
• Servers translate IP packets on the fly as they pass over into internet & back again.
• Advantages
  • Security, Conservation of IP address, prevention of IP spoofing
• Disadvantages
  • Cost, performance, reliability, security

Proxies

• Similar to NAT, but work on the service level
  • not IP level
• Proxy handles specific requests for services
• Advantages
  • Security, reliability
• Disadvantages
  • Scalability, fexibility

IPv6/IPng

• IPv4 is rapidly running out of addresses
• IPv6 is new version of IP designed with following goals in mind
  • Support bilions of hosts
  • Reduce the size of routing tables
  • Simplify the protocol
  • Provide better security
  • Pay more attention to type of service
  • Aid multicasting by allowing scopes to be specified
  • Allow roaming hosts
  • Allow the protocol to evolve
  • Allow coexistence with IPv4

IPv6 Protocol Header

Compare IPv4 versus IPv6