From: mawpz@levels.unisa.edu.au
Newsgroups: unisa.cse.network
Subject: lecturenote4
Date: 4 Sep 92 10:20:53 +0930
Organization: University of South Australia

Chapter 5 The network layer



	not point to point, but
	
	end to end (source to destination) based on point-to-point

Aim of network layer

	provide services to the transport layer

design goals:

	. service should be independent to subnet structure (technology)

	. provide a transparent interface to transport layer

	. uniform naming scheme

Key issues with the services

	connection or conectionless

		accurate or speed delivery

		this connection is different with the data link layer
                it is for end-to-end

	connectionless has:
	
		.simple, 

		.subnet is always unreliable

		.reliable issue leaves for higher layer protocol

	connection has:

		.complex,
		.deal with reliable issue
		.setup, transmit, release three phases

	
The connection or conectionless lead to two services:

	virtual circuit

	datagram

Fig 5-1

	many applications don't need reliable, but speed (voice or image)

Final results in ISO

	support both kind services

Fig 5-2

Network service primitives (between transport and network )

	there are four categories for connection-oriented

	two group for connectionless-oriented

Fig 5-4

option

	QOS: (two lists) for throughput, delay, error rate, etc.

	.expected quality

	.min quality

naming structure

Fig 5-5

or IP number (32 bit) A.B.C.D


Basic function

	1. route packet

	2. conestion control

	3. interconnection of different networks


routing algorithms

	nonadaptive algorithm

	adaptive algorithm

		centrolized

		isolated (based local available information)

		distributed 

example algorithms:

Nonadaptive

1.Shortest path routing

	(refering your data structure )

2.Multipath routing

	Nonadaptive (but you may change it)

	due to a number of routhes have the same quality, 
	the best one depends on how to split the traffic
	and balance the load on different routes.

  Implementation detail

	each IMP has a table, in the table each row for a destination IMP
   as shown in Fig 5-12

	for each packet (or connection establishment request), an IMP

	generates a random number, based on the range of the random

	number, the IMP chooses a route for it

Centralized routing

	every thing is changing, so does network. Therefore
	adaptive methods are introduced.


RCC (route control center) collects the load information 
from each IMP regularly, compute the best routh between IMPs 
based on the data and download them to IMPs

benifit: changeable

suffer: overhead from the collection load, especially for big net
	the failure of RCC or its connection

Fig 5-13
----------------------------------------------------------------------------
 Isolated routing

	hot potato algorithm

	.linking the incoming packet to the shortest queue of the IMP's
	 outline

Fig 5-14

	backward learning

	. incoming packets bring some information about the distance
	between two IMPs

	. the receiver IMP tries to learn whether the incoming packet
	used a shortpath that it was not aware

	. update its route table from the learning

	delta routing

	. combining RCC and isolated routing


Flooding 

	. send the incoming packet to all outlines except the incoming line


		potential uses

		  . consistency for multi-copies of distributed database

		  . for urgent message delivery

Others
	 
	selective flooding/random walk

--------------------------------------------------------------------------------

Distributed Routing

	each IMP keeps a table which records the "distance" from it to its neighbour

	IMPs regularly exchange some estimated info. with its neighbour 


	then, each IMP can know its "distance" to other IMP and
        select a route                                   


	Fig 5-15
-------------------------------------------------------------------------------
Optimal routing

	optimality priniple:

		if two nodes (C, D) on a shortest route from X to Y, then  the link
		between C and D is also the shortest one.

	
	sink tree leads to shortest route tree for a particular distination, and
	
	provides shortest routes for upstream nodes to downstream nodes

	Fig. 5-16 and Fig 5-17

	key problem is if a link is broken
		
		how to recover?

		ask upstream node to link to another branch in the tree 

	each node has a table, 

	 a row for a destination

	 a colume for a neighbour
-------------------------------------------------------------------------------------
Hierarchical routing

	.reduce the size of the table kept by each node (IMP)

	Basic

	a network is divided into regions, region to clusters, cluster to zones

	some gateway machines are used to link different zones/cluster/region

	each IMP knows its local IMPs (include its gateway)

	   for each packet, if it is:

		local, IMP knows how to route

		no local, pass to the gateway to handle
        e.g.


	IP number

Broadcast routing

------------------------------------------------------------------------------------------

Congestion Control

	it tries to solve network's problem, while, flow control is designated for
	point to point

	Potential risk for congestion is dead lock due to the shortage of resource

1) Preallocte buffer

	Each IMP remains at least a/two buffer(s) for each logical line	(simplex/duplex)

	waste many resources.

2) Packet discarding

	oposite to the above (preallocation)

	if no resource for an incoming packet, the packet is discarded

	for VC reliable comm.

		retransmission is needed

	.how to deal with incoming ACK,

		always have one buffer for each line

	.how to allocate buffers for different output line in an IMP

		set a threshold for each output line (it is a hard question)

		. give  potential double and triple the output from this IMP

	.which packet should be discarded

		,new comer in order to save the investment

		Fig. 5-22


--------------------------------------------------------------------------------

Isarithmic congestion control

	. introduces permits ( as token) in the network

	. the number of permits is the same as network capacity

	. permits travals around in the network

	. with one permit, an IMP can send a packet

	problems:

		how to hunt and control the permits? (packets needs to wait permit)

	
Flow control

	flow control is mainly used to control the "overfeeding" problem

-------------------------------------------------------------------------------
deadlock

	Fig. 5-23

---------------------------------------------------------------------------------
Internetworking

	.contain different machines, protocols ...., in internetworks

	.TCP/IP, SNA, LANs will remain for long time despite ISO/OSI

	fig. 5-26
---------------------------------------------------------------------------
	
ISO
 	in the network layer 

	.subnet access sublayer

	.subnet enhancement sublayer

	.internet sublayer

	Fig 5-27


	
------------------------------------------------------------------------------

repeater

bridge

gateway

protocol converter
#! rnews 499