Courses

# Deadlock-free Packet Switching Computer Science Engineering (CSE) Notes | EduRev

## Computer Science Engineering (CSE) : Deadlock-free Packet Switching Computer Science Engineering (CSE) Notes | EduRev

``` Page 1

Dept. of CSE, IIT KGP
-
-
free Packet Switching
free Packet Switching
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Page 2

Dept. of CSE, IIT KGP
-
-
free Packet Switching
free Packet Switching
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Dept. of CSE, IIT KGP
s t u v
Buffer-size = 5
Node s sending 5 packets to v through t
Node v sending 5 packets to s through u
Page 3

Dept. of CSE, IIT KGP
-
-
free Packet Switching
free Packet Switching
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Dept. of CSE, IIT KGP
s t u v
Buffer-size = 5
Node s sending 5 packets to v through t
Node v sending 5 packets to s through u
Dept. of CSE, IIT KGP
Model
Model
â€¢ â€¢ The network is a graph G = (V, E) The network is a graph G = (V, E)
â€¢ â€¢ Each node has Each node has B B buffers buffers
Moves Moves: :
â€¢ â€¢ Generation. Generation. A node A node u u creates a new  packet creates a new  packet p p and places it in and places it in
an empty buffer in an empty buffer in u u. Node . Node u u is the source of is the source of p p. .
â€¢ â€¢ Forwarding. Forwarding. A packet A packet p p is forwarded from a node is forwarded from a node u u to an to an
empty buffer in the next node empty buffer in the next node w w on its route. on its route.
â€¢ â€¢ Consumption. Consumption. A packet A packet p p occupying a buffer in its destination occupying a buffer in its destination
node is removed from the buffer. node is removed from the buffer.
Page 4

Dept. of CSE, IIT KGP
-
-
free Packet Switching
free Packet Switching
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Dept. of CSE, IIT KGP
s t u v
Buffer-size = 5
Node s sending 5 packets to v through t
Node v sending 5 packets to s through u
Dept. of CSE, IIT KGP
Model
Model
â€¢ â€¢ The network is a graph G = (V, E) The network is a graph G = (V, E)
â€¢ â€¢ Each node has Each node has B B buffers buffers
Moves Moves: :
â€¢ â€¢ Generation. Generation. A node A node u u creates a new  packet creates a new  packet p p and places it in and places it in
an empty buffer in an empty buffer in u u. Node . Node u u is the source of is the source of p p. .
â€¢ â€¢ Forwarding. Forwarding. A packet A packet p p is forwarded from a node is forwarded from a node u u to an to an
empty buffer in the next node empty buffer in the next node w w on its route. on its route.
â€¢ â€¢ Consumption. Consumption. A packet A packet p p occupying a buffer in its destination occupying a buffer in its destination
node is removed from the buffer. node is removed from the buffer.
Dept. of CSE, IIT KGP
Requirements
Requirements
The packet switching controller has the following requirements: The packet switching controller has the following requirements:
1. 1. The consumption of a packet (at its destination) is always The consumption of a packet (at its destination) is always
allowed. allowed.
2. 2. The generation of a packet in a node where all buffers are The generation of a packet in a node where all buffers are
empty is always allowed. empty is always allowed.
3. 3. The controller uses only local information, that is, whether a The controller uses only local information, that is, whether a
packet can be accepted in a node packet can be accepted in a node u u depends only on depends only on
information known to information known to u u or contained in the packet or contained in the packet
Page 5

Dept. of CSE, IIT KGP
-
-
free Packet Switching
free Packet Switching
CS60002: CS60002: Distributed Systems Distributed Systems
Pallab Pallab Dasgupta Dasgupta
Dept. of Computer Sc. & Dept. of Computer Sc. & Engg Engg., .,
Indian Institute of Technology Kharagpur Indian Institute of Technology Kharagpur
Dept. of CSE, IIT KGP
s t u v
Buffer-size = 5
Node s sending 5 packets to v through t
Node v sending 5 packets to s through u
Dept. of CSE, IIT KGP
Model
Model
â€¢ â€¢ The network is a graph G = (V, E) The network is a graph G = (V, E)
â€¢ â€¢ Each node has Each node has B B buffers buffers
Moves Moves: :
â€¢ â€¢ Generation. Generation. A node A node u u creates a new  packet creates a new  packet p p and places it in and places it in
an empty buffer in an empty buffer in u u. Node . Node u u is the source of is the source of p p. .
â€¢ â€¢ Forwarding. Forwarding. A packet A packet p p is forwarded from a node is forwarded from a node u u to an to an
empty buffer in the next node empty buffer in the next node w w on its route. on its route.
â€¢ â€¢ Consumption. Consumption. A packet A packet p p occupying a buffer in its destination occupying a buffer in its destination
node is removed from the buffer. node is removed from the buffer.
Dept. of CSE, IIT KGP
Requirements
Requirements
The packet switching controller has the following requirements: The packet switching controller has the following requirements:
1. 1. The consumption of a packet (at its destination) is always The consumption of a packet (at its destination) is always
allowed. allowed.
2. 2. The generation of a packet in a node where all buffers are The generation of a packet in a node where all buffers are
empty is always allowed. empty is always allowed.
3. 3. The controller uses only local information, that is, whether a The controller uses only local information, that is, whether a
packet can be accepted in a node packet can be accepted in a node u u depends only on depends only on
information known to information known to u u or contained in the packet or contained in the packet
Dept. of CSE, IIT KGP
Solutions
Solutions
â€¢ â€¢ Structured solutions Structured solutions
â€“ â€“ Buffer Buffer- -graph based schemes graph based schemes
â€¢ â€¢ The destination scheme The destination scheme
â€¢ â€¢ The hops The hops- -so so- -far scheme far scheme
â€¢ â€¢ Acyclic orientation based scheme Acyclic orientation based scheme
â€¢ â€¢ Unstructured solutions Unstructured solutions
â€“ â€“ Forward count and backward count schemes Forward count and backward count schemes
â€“ â€“ Forward state and backward state schemes Forward state and backward state schemes
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;