04-network Layer-02 By Apcoms

CPS 422 Computer Networks

Network Layer - Classes of Service ‰Network Layer provides two classes of services o Connection oriented o Connection-less

‰A connection is usually called a virtual circuit (VC) ‰The independent packets of a connectionless service are called datagrams ‰In a VC all packets follow the same route from source to destination ‰In a connectionless service all packets (datagrams) are routed independent of each other

NETWORK LAYER

Faisal Amjad CPS 422

Comparison of VC and datagram subnets Issue

Datagram Subnet

VC Subnet

Circuit setup

Not needed

Required

Addressing

Each packet contains source destination address

Each packet contains a short VC number

State information

Subnet does not hold

Each VC requires a table space

Routing

Each packet routed independently

Route chosen at circuit setup, all packets follow it

Effect of router failure

None, except for packets lost during the crash

All VCs at point of failure are terminated

Congestion control

Difficult

Easy because buffers are allocated in advance for each VC

Faisal Amjad CPS 422

Routing Algorithm and its Properties ‰ Properties required from a Routing protocol are o o o o o o

Correctness Simplicity Robustness Stability Fairness Optimality

‰ Without correctness a routing protocol is useless ‰ A simple protocol is an efficient one, that requires less processing at the router ‰ Robustness: Once a network comes up, it may undergo changes, failures etc. many times. The routing protocol must be able to handle all sorts of changes, without requiring all jobs to be aborted and system rebooting Faisal Amjad CPS 422

Faisal Amjad CPS 422

Routing and Classes of service ‰ The main function of the network layer is routing packets from source to destination machine ‰ In most of the cases, packets will require multiple hops to make this journey ‰ Hence, Routing algorithm is that part of network layer software, responsible for deciding which output line an incoming packet should be transmitted on ‰ For subnets using datagrams (e.g. IP) this decision is made anew for every arriving data packets since the best route may have changed since the last time ‰ For subnets employing VCs (e.g. ATM based networks), the routing decision is made at circuit setup time ‰ Data packets in this case follow the previously established route ( also called session routing ) Faisal Amjad CPS 422

Routing Algorithm and its Properties

(Contd)

‰Stability is an important goal, an algorithm must come to conclusion quickly, so that routing decisions are not held up for long ‰Fairness means all hosts’ traffic is treated equally ‰Optimality means that the network resources are utilized to their maximum efficiency ‰Fairness and optimality are often contradicting goals

Faisal Amjad CPS 422

1

Conflict between fairness and optimality A

B

C

C1

A1

B1

Faisal Amjad CPS 422

Routing Algorithms and their Classes ‰ Two classes of routing algorithms o Non adaptive algorithms and o Adaptive algorithms

‰ Non-adaptive algorithms do not base their routing decisions on estimates of current traffic or topology. ‰ The choice of routes is computed in advance, off-line and downloaded to the routers when the network is booted. This is also called static routing ‰ Adaptive routing algorithms change their routing decisions to reflect changes in topology and traffic conditions ‰ Adaptive algorithms differ in o From where they get routing information o When do they change routes o What metric is used for optimization

Routing Algorithm and its Properties

(Contd)

‰What do we need to optimize??? ‰One metric could be mean packet delay ‰Another one could be network throughput ‰But both of them are again conflicting goals ‰Increasing network throughput would mean having more and more packets in the buffers of the routers so that they do not sit idle ‰However this would increase mean packet delay ‰To reduce mean packet delay we should have a smaller queue at the routers ‰Hence these two goals prove to be in contradiction

Faisal Amjad CPS 422

Shortest Path Routing ‰A widely used, static routing algorithm ‰The idea is to build a graph of the subnet, with each node of the graph representing a router and each arc representing a communication link. ‰To choose a route between given routers, the algorithm finds the shortest path ‰The “shortest path” may be computed on the basis of number of hops, the distance, bandwidth available, queue lengths etc. ‰Any number of metrics can be used for shortest path calculation

Faisal Amjad CPS 422

Faisal Amjad CPS 422

Dijkstra’s Algorithm - Shortest Path Routing ‰Each node is labeled (in parenthesis) with its distance from the source node along the best known path ‰Initially no paths are known so the nodes are labeled with infinity ‰As the algorithm proceeds, paths are found and labels changed, reflecting better paths. ‰A label may be tentative or permanent. ‰Initially all labels are tentative, but made permanent when they are established as shortest paths. Faisal Amjad CPS 422

B 2

C

7 2

E

A 6

2

3

D 2

1

G

F

3

4

2

H

‰ We want to find the shortest route from A to D ‰ A is the starting node, made permanent by a filled circle ‰ All links are labeled with the distance from adjacent nodes ‰ All nodes adjacent to A will be considered in this run, in this case B and G

Faisal Amjad CPS 422

2

B (2,A) 2

2

E( ∞,-)

A 6

C ( ∞,-)

7 2

G (6,A)

3

F( ∞,-) 2

1 4

B (2,A)

3

2

D ( ∞,-)

2

E( ∞,-)

A 6

2

‰ We have labeled all the nodes of the graph ‰ Nodes adjacent to A are labeled with their distance from A, alongwith the node identity from which this probe was made ‰ Nodes not adjacent to A are labeled with infinity

2

3

3

F( ∞,-) 2

1

G (6,A)

H ( ∞,-)

C ( ∞,-)

7

4

D ( ∞,-) 2

H ( ∞,-)

‰ Node with a Label having the shortest path will be made permanent, in this case B (indicated by a filled circle) ‰ This node (B) now becomes the working node and subsequent probe will be made from it

Faisal Amjad CPS 422

B (2,A) 2

2

E( 4,B) 2

A 6

7

G (6,A)

C ( 9,B) 3

F( ∞,-)

4

B (2,A)

3

2

1

Faisal Amjad CPS 422

2

D ( ∞,-)

2

E( 4,B) 2

A 6

2

‰ All nodes adjacent to B are probed and labels now changed according to their distances ‰ Node with the label having shortest distance will be made permanent next ‰ Which node (with a tentative label) has the shortest distance label ??

C ( 9,B) 3

3

F( 6,E) 2

1

G (6,A) G (5,E)

H ( ∞,-)

7

4

D ( ∞,-) 2

H ( ∞,-)

‰ All nodes adjacent to E are probed and labels now changed according to their distances ‰ Note that the label of G has to change since its distance is lesser from E (5) rather than directly from A (6)

Faisal Amjad CPS 422

B (2,A) 2

2

E( 4,B) 2

A 6

7

G (5,E)

C ( 9,B) 3

4

B (2,A)

3

F( 6,E) 2

1

Faisal Amjad CPS 422

2

D ( ∞,-)

2

‰ Now all tentative nodes are scanned and the one with shortest distance will be made permanent, and made the working node

Faisal Amjad CPS 422

C ( 9,B) 3

4

3

F( 6,E) 2

1

G (5,E)

H ( ∞,-)

E( 4,B) 2

A 6

2

7

D ( ∞,-) 2

H ( 9,G)

‰ Now all neighbors of G are probed and labeled, in this case H

Faisal Amjad CPS 422

3

B (2,A) 2

2

E( 4,B) 2

A 6

7

C ( 9,B) 3

F( 6,-E 2

1 4

G (5,E)

B (2,A)

3

2

D ( ∞,-)

Faisal Amjad CPS 422

B (2,A) 2

E( 4,B) 2

A 6

7

G (5,E)

4

3

4

3

F( 6,E)

D ( ∞,-) 2

H ( 8,F)

‰ Since H has smallest distance, it is made permanent

Faisal Amjad CPS 422

C ( 9,B) 3

3

F( 6,E) 2

1

C ( 9,B)

2

1

G (5,E)

H ( 9,G)

E( 4,B) 2

A 6

2

‰ Since F has smallest distance, it is made permanent

2

2

7

D ( 10,H) 2

H ( 8,F)

‰ Since H has smallest distance, it is made permanent ‰ In the next run D will have the shortest path from H (10) ‰ At the end the shortest path will be constructed from the labels already made permanent ‰ DHFEBA will at the end be reversed to get the (forward) shortest path Faisal Amjad CPS 422

4