32 by 32 toroid: 32 hops (16 horizontal and 16 vertical).5th order tetrahedral pyramid: 31 hops. In fact, always 1 less than a toroid of the same number of vertices. In effect, the recursive tetrahedral pyramid has path lengths charactristic of a 2-dimensional structure!
Part b: For each of the above, what is the minimum number of carefully chosen links that must be broken to partition the network into two independent networks.
32 by 32 toroid: to isolate one vertex from the remainder, cut 4 links, to split the net in 2 equal sized fragments, cut 32 links.5th order tetrahedral pyramid: To isolate one outside corner vertex at any level of the pyramid, cut 3 links. To split the pyramid in half, cut 4 links.
Part c: Given that messages are addressed with a 10 bit destination address, suggest an address assignment scheme for these networks that leads to a relatively simple message forwarding algorithm.
32 by 32 toroid: The address has 2 fields, 5 bits each, for the row and column. If a message arrives at vertex v, where the address a is not equal to v, if the row field is equal, forward to the correct row, otherwise, forward along the column to vertex a. For both row and column forwarding, compute (a-v)mod 32; if this is less than 16, forward to the next higher neighbor in the row (or column); if it higher, forward to the next lower neighbor.5th order tetrahedral pyramid: The address is composed of 5 2-bit fields; each vertex at any level in the pyramid can be labeled left, right, top or back; these correspond to 00, 01, 10 and 11 in the binary code. The least significant 2 bits give the address in the first-order tetrahedron; the next to the least give the address in the second-order tetrahedron, etc. Each machine has outgoing network links labeled to the left, to the right, to the top or to the rear. When a message arrives at vertex v, where the address a is not equal to v, find the most significant 2-bit component of the address that differs from the destination, and then send the message out the link corresponding to that 2-bit field of a.
The kernel could signal a semaphore provided by the user when it is finished with the user's buffer, or (for an inferior solution) the kernel could set a bit associated with the buffer, or (useful but not as easy to implement) the kernel could offer a service allowing the user to inquire if any I/O operations are still pending to a particular address in that user's address space.Also give a clear explanation of what overhead is reduced by the decision to use buffers in the user's address space.
A nonblocking send operation that doesn't transmit directly from the user's address space must copy the data to be sent into a buffer in the system's address space. This adds to the computational cost of interprocess communication and it adds to the storage requirements of the system.
The CSMA-CD protocols developed for Ethernet work well here. Each machine is always listening to the line, even while transmitting. A machine never starts to transmit until it has seen no data for at least one character time; after transmitting each byte, the machine checks the receiver to see if it has received the byte it just transmitted. If it does not receive exactly the same byte, some other machine may have transmitted, so such an error is treated as a collision, leading to an attempt to retransmit the entire message after a random delay.