This page was generated using an imperfect translator. Text may be poorly positioned and mathematics will be barely readable. Illustrations will not show at all. If possible, view the PostScript versions of these notes.
5-1 *
* 5-1
Abstract Network Representations
Three commonly used:
- Link-graph model.
- Crosspoint-graph model.
- Sets-of-permutations model.
Uses of Abstract Representations
- Precisely describing network.
- Determining network properties.
Isomorphism. (Similarity of two networks.)
5-1 EE 7725 Lecture Transparency. Formatted 16:38, 10 October 1996 from lsli11.*
* 5-1
5-2 *
* 5-2
Link-Graph Model (LGM)
Similar to direct-network graphs.
Network specified by four-tuple: (I; O; V; E) where:
V is a set of nodes, (each representing a cell, input, or output);
I V is a set of distinguished nodes, called inputs;
O V is a set of distinguished nodes, called outputs and;
E V V is a set of directed edges, (each representing a link).
The order in which links connect to cell is not modeled.
Simple Example
I = fhI; 0i ; hI; 1i g
O = fhO; 0i ; hO; 1i g
V = fhI; 0i ; hI; 1i ; hO; 0i ; hO; 1i ; h0; 0i g
E = f(hI; 0i ; h0; 0i ); (hI; 1i ; h0; 0i ); (h0; 0i ; hO; 0i ); (h0; 0i ; hO; 1i *
* )g
5-2 EE 7725 Lecture Transparency. Formatted 16:38, 10 October 1996 from lsli11.*
* 5-2
5-3 *
* 5-3
MIN LGM Example
(2; 2; 2; S; T ) network:
Node notation: hstage no. or I or O, cell no. i.
I = fhI; 0i ; hI; 1i ; hI; 2i ; hI; 3i g O = fhO; 0i ; hO; 1i ; hO; 2i ; hO; 3i g
Stage-zero cell labels: fh0; 0i ; h0; 1i g.
V = f hI; 0i ; hI; 1i ; hI; 2i ; hI; 3i ; hO; 0i ; hO; 1i ;
hO; 2i ; hO; 3i ; h0; 0i ; h0; 1i ; h1; 0i ; h1; 1i g:
E = f (hI; 0i ; h0; 0i ); (hI; 1i ; h0; 1i ); (hI; 2i ; h0; 0i ); (hI; 3i ; h0; 1*
*i );
(h0; 0i ; h1; 0i ); (h0; 0i ; h1; 1i ); (h0; 1i ; h1; 0i ); (h0; 1i ; h1; 1*
*i );
(h1; 0i ; hO; 0i ); (h1; 0i ; hO; 1i ); (h1; 1i hO; 2i ); (h1; 1i hO; 3i*
* )g:
5-3 EE 7725 Lecture Transparency. Formatted 16:38, 10 October 1996 from lsli11.*
* 5-3
5-4 *
* 5-4
LGM of an (n; m; mn1 ; S; T ) Omega Network
Let k = mn1 , as usual.
I = f hI; ii j 0 i < mk g
O = f hO; ii j 0 i < mk g
V = I [ O [ f hx; ii j 0 x < n; 0 i < k g
The edges are the interesting part:
E = f (hI; ii ; h0; i mod ki ) j 0 i < mkg[
f (hx; ii ; hx + 1; mi + j mod ki ) j
0 j < m; 0 i < k; 0 x < n 1 g[
f (hn 1; ii ; hO; mi + ji ) j 0 j < m; 0 i < k g
5-4 EE 7725 Lecture Transparency. Formatted 16:38, 10 October 1996 from lsli11.*
* 5-4
5-5 *
* 5-5
Crosspoint-Graph Model (CGM)
Not similar to direct-network graphs.
Network specified by four-tuple: (I; O; V; E) where:
V is a set of nodes, (each representing a link);
I V is a set of distinguished nodes, called inputs;
O V is a set of distinguished nodes, called outputs and;
E V V is a set of directed edges, (each representing a cross-
point).
Simple Example
I = fhI; 0i ; hI; 1i g
O = fhO; 0i ; hO; 1i g
V = fhI; 0i ; hI; 1i ; hO; 0i ; hO; 1i g
E = f(hI; 0i ; hO; 0i ); (hI; 0i ; hO; 1i ); (hI; 1i ; hO; 0i ); (hI; 1i ; hO; 1i*
* )g
5-5 EE 7725 Lecture Transparency. Formatted 16:38, 10 October 1996 from lsli11.*
* 5-5
5-6 *
* 5-6
(2; 2; 2; S; T ) MIN CGM Example
Network links ! graph nodes:
V = f hI; 0i ; hI; 1i ; hI; 2i ; hI; 3i ; h0; 0i ; h0; 1i ; h0; 2i ; h0; 3i ;
hO; 0i ; hO; 1i ; hO; 2i ; hO; 3i :
Stage-0; cell-0 crosspoints ! graph edges:
f(hI; 0i ; h0; 0i ); (hI; 0i ; h0; 1i ); (hI; 2i ; h0; 0i ); (hI; 2i ; h0; 1i )g
All crosspoints ! graph edges:
E = f (hI; 0i ; h0; 0i ); (hI; 0i ; h0; 1i ); (hI; 2i ; h0; 0i ); (hI; 2i ; h0; 1i*
* );
(hI; 1i ; h0; 2i ); (hI; 1i ; h0; 3i ); (hI; 3i ; h0; 2i ); (hI; 3i ; h0; 3i*
* );
(h0; 0i ; hO; 0i ); (h0; 0i ; hO; 1i ); (h0; 1i ; hO; 2i ); (h0; 1i ; hO;*
* 3i );
(h0; 2i ; hO; 0i ); (h0; 2i ; hO; 1i ); (h0; 3i ; hO; 2i ); (h0; 3i ; hO;*
* 3i )g
5-6 EE 7725 Lecture Transparency. Formatted 16:38, 10 October 1996 from lsli11.*
* 5-6
5-7 *
* 5-7
Networks Using Incomplete Crossbars
These can be represented using the CGM but cannot be represented
using the LGM.
A crossbar is incomplete if there is at least one input/output pair that
cannot be connected.
5-7 EE 7725 Lecture Transparency. Formatted 16:38, 10 October 1996 from lsli11.*
* 5-7
5-8 *
* 5-8
Miscellaneous Topic: Connection Assignments
Important network characteristic: which sets of requests can be si-
multaneously routed?
Connection Assignment (CA)- A set of requests.
For example, f(1; 2); (2; 4)g.
Usually, one intends to simultaneously use all requests in a con-
nection assignment.
Permutation Connection Assignment- A set of requests for a network
in which each input and each output appear exactly once.
For example, for a 3 input network:
f(0; 1); (2; 0); (1; 2)g is a permutation CA.
f(0; 1); (0; 0); (1; 2)g is not a permutation CA (because in-
put 0 connects to two outputs and input 2 does not
appear).
A network satisfies a connection assignment if there are non-conflicting
paths for all requests.
If a network can satisfy a CA then the communication can be
handled most efficiently.
If a network cannot satisfy a CA then either:
There will be delay as some messages must wait in queues.
(In the packet switching systems we have studied.)
The CA must be broken into two or more CAs, which then
must be satisfied one at a time. (In the circuit switch-
ing systems we will soon be studying.)
5-8 EE 7725 Lecture Transparency. Formatted 16:38, 10 October 1996 from lsli11.*
* 5-8
5-9 *
* 5-9
Graph Models and Connection Assignments
A network can satisfy a connection assignment if there exist edge-
disjoint paths in the network's LGM for all requests in the con-
nection assignment.
A network can satisfy a connection assignment if there exist node-
disjoint paths in the network's CGM for all requests in the con-
nection assignment.
5-9 EE 7725 Lecture Transparency. Formatted 16:38, 10 October 1996 from lsli11.*
* 5-9
5-10 *
* 5-10
Sets of Permutations Model
Set of all possible permutation connection assignments that the net-
work can satisfy.
Covered in detail soon.
Comparison of Models
LGM might seem more natural.
CGM more powerful.
Set-of-permutations model is useful for studying what networks can
do.
5-10 EE 7725 Lecture Transparency. Formatted 16:38, 10 October 1996 from lsli1*
*1. 5-10
| David M. Koppelman - koppel@ee.lsu.edu | Modified 10 Oct 1996 16:38 (21:38 UTC) |