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 Abstract Network Representations *
* 5-1
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 13:48, 8 October 1997 from l*
*sli11. 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.
5-2 EE 7725 Lecture Transparency. Formatted 13:48, 8 October 1997 from l*
*sli11. 5-2
5-3 *
* 5-3
Link-Graph Model Simple Example
I = fhI; 0i; hI; 1ig
O = fhO; 0i ; hO; 1ig
V = fhI; 0i; hI; 1i; hO; 0i ; hO; 1i ; h0; 0ig
E = f(hI; 0i; h0; 0i); (hI; 1i; h0; 0i); (h0; 0i ; hO; 0i); (h0; 0i ; hO; 1i)g
5-3 EE 7725 Lecture Transparency. Formatted 13:48, 8 October 1997 from l*
*sli11. 5-3
5-4 *
* 5-4
MIN LGM Example
A (2; 2) omega network: *
* __
Node notation:
hstage no. or I or O, cell no.i.
I = fhI; 0i ; hI; 1i; hI; 2i; hI; 3ig
O = fhO; 0i ; hO; 1i ; hO; 2i ; hO; 3i g
Stage-zero cell labels:
fh0; 0i ; h0; 1ig.
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; 1ig:
E = f (hI; 0i; h0; 0i); (hI; 1i; h0; 1i); (hI; 2i; h0; 0i); (hI; 3i; h0; 1i);
(h0; 0i ; h1; 0i); (h0; 0i ; h1; 1i); (h0; 1i ; h1; 0i); (h0; 1i ; h1; 1i);
(h1; 0i ; hO; 0i); (h1; 0i ; hO; 1i); (h1; 1i hO; 2i); (h1; 1i hO; 3i)g:
5-4 EE 7725 Lecture Transparency. Formatted 13:48, 8 October 1997 from l*
*sli11. 5-4
5-5 *
* 5-5
LGM of an (m; n) Omega Network
Let k = mn1 , as usual.
I = f hI; iij 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-5 EE 7725 Lecture Transparency. Formatted 13:48, 8 October 1997 from l*
*sli11. 5-5
5-6 *
* 5-6
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 crosspoint).
5-6 EE 7725 Lecture Transparency. Formatted 13:48, 8 October 1997 from l*
*sli11. 5-6
5-7 *
* 5-7
CGM Simple Example
I = fhI; 0i; hI; 1ig
O = fhO; 0i ; hO; 1ig
V = fhI; 0i; hI; 1i; hO; 0i ; hO; 1ig
E = f(hI; 0i; hO; 0i); (hI; 0i; hO; 1i); (hI; 1i; hO; 0i); (hI; 1i; hO; 1i)g
5-7 EE 7725 Lecture Transparency. Formatted 13:48, 8 October 1997 from l*
*sli11. 5-7
5-8 *
* 5-8
Small Omega 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 g:
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-8 EE 7725 Lecture Transparency. Formatted 13:48, 8 October 1997 from l*
*sli11. 5-8
5-9 *
* 5-9
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 con-
nected.
5-9 EE 7725 Lecture Transparency. Formatted 13:48, 8 October 1997 from l*
*sli11. 5-9
5-10 *
* 5-10
Miscellaneous Topic: Connection Assignments
Important network characteristic:
Which sets of requests can be simultaneously routed?
Connection Assignment (CA)
A set of requests, for example, f (1; 2); (2; 4) g.
Typically, network must simultaneously handle every request in a CA.
5-10 EE 7725 Lecture Transparency. Formatted 13:48, 8 October 1997 from *
*lsli11. 5-10
5-11 *
* 5-11
Permutation Connection Assignment
A connection assignment 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 input 0 connects to two outputs and input 2 does not appear).
5-11 EE 7725 Lecture Transparency. Formatted 13:48, 8 October 1997 from *
*lsli11. 5-11
5-12 *
* 5-12
A network satisfies a connection assignment : : :
: : :if there are non-conflicting paths for all requests.
Non-conflicting usually means link-disjoint.
If a network can satisfy a CA then the communication can be handled most efficiently.
If a network cannot satisfy a CA then:
In packet networks, there will be delay as some messages must wait in queues.
In circuit switched networks, the CA must be broken into two or more CAs : : :
: : :which then must be satisfied one at a time.
5-12 EE 7725 Lecture Transparency. Formatted 13:48, 8 October 1997 from *
*lsli11. 5-12
5-13 *
* 5-13
Graph Models and Connection Assignments
Represented Using LGM Models
Can satisfy a CA if there exist
edge-disjoint paths for all requests.
Represented Using CGM Models
Can satisfy a CA if there exist
node-disjoint paths for all requests.
5-13 EE 7725 Lecture Transparency. Formatted 13:48, 8 October 1997 from *
*lsli11. 5-13
5-14 *
* 5-14
Sets of Permutations Model
Set of all possible permutation connection assignments that the network 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-14 EE 7725 Lecture Transparency. Formatted 13:48, 8 October 1997 from *
*lsli11. 5-14
| David M. Koppelman - koppel@ee.lsu.edu | Modified 8 Oct 1997 13:49 (18:49 UTC) |