Technical reports

Binary routing networks

David Russel Milway

December 1986, 131 pages

This technical report is based on a dissertation submitted December 1986 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Darwin College.

DOI: 10.48456/tr-101

Abstract

Binary Routing Networks combine ideas from Wide Area Networks and Interconnection Networks with the principles of Local Area Networks. This results in a high performance network for use in the local and wide area environment. Simulation of this form of network shows that for certain structures the performance of the network can approach or even exceed that obtained from a cross-bar switch. This dissertation describes how network structures based on Binary Routing Networks can be used in applications where a network capable of high rates of throughput with low delay is required.

Binary Routing Networks use a switching fabric constructed from simple routing nodes to route packets from a source to a destination. Some network topologies allow many packets to pass through the network simultanously, giving the network an aggregate throughput mugh greater than the basic bit rate. Routing nodes do not require knowledge of the topology and are thus simple to construct. They use routing information in the packet to direct the packet through the network. Packets pass through the nodes with little delay except where contention for a link occurs when the packet needs to be buffered.

A design for a non-buffered routing node is described where contention is resolved by discarding one of the packets. Discarded packets are retried later by the sending station. This form of network removes the buffers from the routing nodes making them even simpler to construct. Simulations of a network of 512 stations show that for loads per station of up to 20% of the basic bit rate, a non-buffered network can outperform a buffered network. This design allows the construction of a fault tolerant network which can pass packets through any number of different paths, avoiding broken links or congensted areas in the network.

A prototype of a Binary Routing Network is discussed. This network makes use of the non-buffered routing nodes and measurements of its performance are compared with results obtained from the simulations. A proposal for using this form of network in an Integrated Service environment are also given.

Structures similar to Binary Routing Networks are fast becoming the backbone of multiprocessor systems. Local Area Networks also need to apply this technology to meet the requirements that they are being asked to support.

Full text

PDF (7.9 MB)

BibTeX record

@TechReport{UCAM-CL-TR-101,
  author =	 {Milway, David Russel},
  title = 	 {{Binary routing networks}},
  year = 	 1986,
  month = 	 dec,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-101.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-101},
  number = 	 {UCAM-CL-TR-101}
}