Packet Switching Networks-2

By -

UNIT II- Packet Switching Networks-2

Link-State Algorithm

• Basic idea: two stage procedure

• Each source node gets a map of all nodes and link metrics (link state) of the entire network

-Learning who the neighbors are and what are delay to them

- Construct a link state packet, and deliver it to other

• Find the shortest path on the map from the source node to all destination nodes;

-Dijkstras algorithm Broadcast of link-state information

-Every node i in the network broadcast to every other node in the network:

• It requires each link cost to be positive

• The main idea is to progressively identify the closest nodes from source node in order of increasing path cost

• The algorithm is iterative.

• The algorithm can be implemented by maintaining a set of N permanently labeled nodes, which consists of those nodes whose shortest paths have been determined.

• At each iteration the next closest node is added to the set N and the distance to the remaining nodes via the new node is evaluated.

Dijkstra Algorithm:

Finding shortest paths in order

· N: set of nodes for which shortest path already found

· Initialization: (Start with source node s)

· N = {s}, Ds = 0, “s is distance zero from itself”

· Dj=Csj for all j ¹ s, distances of directly-connected neighbors

· Step A: (Find next closest node i)

  • · Find i Ï N such that
  • · Di = min Dj for j Ï N
  • · Add i to N
  • · If N contains all the nodes, stop

· Step B: (update minimum costs)

  • · For each node j Ï N
  • · Dj = min (Dj, Di+Cij)
  • · Go to Step A

Execution of Dijkstra’s algorithm

image

image

Assignment Questions

1. Why is packet switching more suitable than message switching for interactive applications? Compare the delays in datagram packet switching and message switching. (Jan 10, 6M) (Dec 12 10 M)

2. Differentiate between virtual circuits and datagram subnets.

(July 09, 10M)(AUG 02,Feb 06 6M) (July 07, 5M)

3. Define routing. Explain Bellman-Ford routing algorithm with necessary illustration. What are the drawbacks of this algorithm? (Aug 06, 10M) (June 12 10 M)

4. Explain Bellman-Ford routing algorithm with necessary illustration. What are the drawbacks of this algorithm?

(Aug 06, 10M) (June 12 10 M)

Find the shortest path for below diagrams. Destination node is E for Fig1 and Destination node is 6 for Fig2

image

6. Compare the Bellman –Ford algorithm and Dijkstra’s algorithm for finding the shortest paths from a source node to all other nodes in a network.

7. Good news spreads fast; bad news propagates slowly in bellman ford algorithm.

Explain with an example.

8. Write short notes on i) Flooding ii) Deflection Routing iii) Hierarchical routing.

Comments

Post a Comment

Popular posts from this blog

Packet Switching Networks part2

By -
Image
ROUTING TABLES Routing Table for Virtual circuit networks • virtual circuit identifier determines the destination Routing table for datagram networks Specialized Routing Flooding · Principle of flooding : a node (or a packet switch) forwards an incoming packet to all ports except to the one it arrived on. · Each node (a switch) performs the flooding process such that the packet will reach the destination as long as at least one path exists between the source and the destination. · Flooding is a useful o when the information in the routing tables is not available, such as during system startup, o when survivability is required, such as in military networks. o when the source needs to send a packet to all hosts connected to the network (i.e., broadcast delivery). • Flooding generates vast numbers of duplicate packets In figure, initially one packet arriving at node 1 triggers three packets to nodes 2, 3, and 4. In the second phase nodes 2, 3, and 4 send two, two, and thre...
Read more

TCP/IP-II:OSPF Link State Update

By -
Image
OSPF Link State Update In response to LS request or trigger router will send new LS info trigger, using the LS update message Contents are composed of link state advertisements (LSA’s) LS update message is acknowledged using LS ack pkt to ensure that the flooding algorithm is reliable; Link state acknowledgement packets consist of a list of LSA headers. BGP (Border Gateway Protocol): The de facto standard for inter-AS routing, BGP: glues the whole Internet together   P ath Vector protocol Uses TCP (service port: 179) Similar to Distance Vector protocol. Each Border Gateway broadcast to neighbors (peers) e ntire path (i.e., sequence of AS’s) to destination BGP is an exterior gateway protocol (EGP), which means that it performs routing between multiple autonomous systems or domains and exchanges routing and reachability information with other BGP systems. The information exchanged among BGP routers allow a router to construct a graph of AS’s and each AS...
Read more

Packet Switching Networks:Traffic Management

By -
Image
Traffic Management · The main objectives of traffic management are efficient use of network resources & deliver QoS. · Traffic Management is classified into three levels that are Packet level, Flow level and  Flow aggregated level. Traffic Management at Packet Level o Queueing & scheduling at switches, routers and multiplexers. The path traversed by packet through a network can be modeled as sequence of Queueing systems as shown in above figure. A packet traversing network encounters delay and possible loss at various multiplexing points. End-to-end performance is sum of the individual delays experienced at each system. Average end-to-end delay is the sum of the individual average delay. To meet the QoS requirements of multiple services, a queueing system must implement strategies for controlling the transmission bit rates. The different strategies for Queue scheduling are:- 1. FIFO QUEUEING 2. PRIORITY QUEUEING 3. FAIR QUEUEING 4. WEIGHTED FAIR...
Read more