A d-dimensional hypercube is a network with N=2^d nodes represented by a d-bit a

Question

A d-dimensional hypercube is a network with N=2^d nodes represented by a d-bit address. Edges exist between node i and every other node that differs in the address exactly by one bit. Thus, each node is connected to exactly d other nodes. A d-dimensional hypercube is to be embedded as a logical topology on a broadcast star network.

(a) what is the number of transmitters and receivers required per node if there is no time-sharing of wavelengths? What is the number of wavelengths required?

(b) Assume that a shortest path is used to route a packet between any two nodes. Describe a routing algorithm, that is , present an algorithm for routing at each node that is based on the destination address of a packet.

(c)How many shortest paths exist between a pair of nodes that differ in their address by k bits. Two paths are said to be different if the sets of edges in the two paths are not identical.

Explanation / Answer

#include #include typedef struct hypercube_details { int max_islands; // Will contain how many islands (power of 2) unsigned int max_degree; // Will contain the maximum degree of connectivity unsigned int max_dimensions; // Will contain max number of bits for address space unsigned int ** map; // mapping, 2d array : map[ an island ][ to max_degree ] } hypercube_struct_t; int makeHypercube( hypercube_struct_t * hc_ptr, int islands ); void freeHypercube( hypercube_struct_t * hc_ptr ); int main(void) { int source, connection; // Create the hypercube variable hypercube_struct_t hypercube; // Call the make function. if( makeHypercube( &hypercube, 64) == 0 ) { printf("Something went wrong :( "); } else { // example usage: // For each node/island. for( source = 0; source max_islands); // The degree is how many other nodes one node connects too hc_ptr->max_degree = log2(hc_ptr->max_islands); printf("Max degree should be %d ", hc_ptr->max_degree); // Work out what power of base 2 this number is. d_temp = log2(hc_ptr->max_islands)/log2(2); hc_ptr->max_dimensions = (unsigned int)d_temp; if( d_temp - (double)hc_ptr->max_dimensions > 0.001 ) { printf("Error: Number of islands is not a power of 2, abort "); return 0; } printf("Max Dimensions %d ", hc_ptr->max_dimensions); // We create a number of bit masks equal to the maximum bits // required to map the addresses in binary. mask = malloc( hc_ptr->max_dimensions * sizeof( unsigned int )); mask[0] = 1; for( dimension = 1; dimension max_dimensions; dimension++ ) { mask[dimension] = (int)pow(2,dimension); } // We create a look up table map for each island, with the // max number of degree entries. hc_ptr->map = malloc( hc_ptr->max_islands * sizeof( unsigned int *)); for( source = 0; source map[source] = malloc( hc_ptr->max_degree * sizeof( unsigned int )); } // We iterate through all the combinations and check for just a one // bit change between addresses, saving to our map table. // We check that we dont create more address mappings than we malloc'd // by tracking the degree variable. This shouldn't happen, but just to // be safe :) for( source = 0; source max_islands; source++ ) { degree = 0; for( target = 0; target max_islands; target++ ) { for( dimension = 0; dimension max_dimensions; dimension++ ) { if( (source ^ target) == mask[dimension] ) { if( degree > hc_ptr->max_degree ) { freeHypercube( hc_ptr ); printf(" Error, found an address match beyond the max degrees, abort "); return NULL; } else { hc_ptr->map[source][degree] = target; degree++; } } } } } free( mask ); } void freeHypercube( hypercube_struct_t * hc_ptr ) { int i; for( i = 0; i max_islands; i++ ) { free( hc_ptr->map[i] ); hc_ptr->map[i] = NULL; } free( hc_ptr->map ); hc_ptr->map = NULL; return; }

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.