Deadlock-free Packet Switching - Computer Science Engineering (CSE) PDF Download

 Page 1


Dept. of CSE, IIT KGP
Deadlock
Deadlock
-
-
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
Deadlock
Deadlock
-
-
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
Store and forward deadlock
Store and forward deadlock
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
Deadlock
Deadlock
-
-
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
Store and forward deadlock
Store and forward deadlock
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
Deadlock
Deadlock
-
-
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
Store and forward deadlock
Store and forward deadlock
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
Deadlock
Deadlock
-
-
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
Store and forward deadlock
Store and forward deadlock
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