Please note that this project is no longer accepting students.
Existing hierarchical routing schemes, employing distance vector and link state routing algorithms, require the exchange of routing information for the construction and maintenance of routing tables. As networks increase in size, the memory requirements for the routing tables and the time taken to search the tables increase proportionally. Further, as the popularity of computer networks increases, the size of the address space can become a limiting factor. Although many Internet routers employ specialized caches to hold recently-used addresses, table search times can degenerate to O(log(n)) and O(n), for ordered and unordered tables, respectively. Furthermore, routers become the bottleneck in high-speed optical networks since packets must be converted from the network's media (light) to the router's media (electrical).
A Cartesian network consists of a 2D-mesh of collectors and arterials. A collector is a 'horizontal' network (running east-west), connecting collector routers, while an arterial is a 'vertical' network (running north-south) that intersects collectors. An arterial router connects collectors and arterials; to ensure connectivity, an arterial is not permitted to bypass a collector.
The above diagram is an example of a simple Cartesian network. The blue circles are collector routers, while the yellow circles are arterial routers. The collector routers are connected by the horizontal black lines and the arterial routers are connected by the red lines.
Cartesian routing is a novel packet routing methodology in which a packet's route is determined by the position of the router relative to that of the destination. Cartesian routing differs from existing provider-based unicast routing in that routing tables are unnecessary since communications are topologically dependent, thereby potentially reducing router and network overheads. Routing decisions are reduced to O(1) in Cartesian routing.
In addition to the unicast routing algorithm, we have developed a protocol for the transmission of broadcast packets on Cartesian networks. The protocol is loop-free and ensures that broadcast packets visit each Cartesian router at most once, by dynamically creating a spanning tree. The protocol requires no additional state information other than that already employed by the existing Cartesian unicast protocol.
A web-based visualization tool that demonstrates the operations of a Cartesian network is available from is2.dal.ca/~rtmurphy. The tool allows the user to design a Cartesian network. The network topology is validated as the network is being built; once built, the user can choose packet source(s) and destination(s) and then run the network. After the network initilizes itself and begins routing packets, the user can choose new packet source(s) and destination(s), simulate link failure and recovery, and examine router status (since each router is an object that maintains statistics on its reachability as well as the number of packets handled).
A wide variety of graduate research projects are available; including:
For a partial list of the research tools and requirements for completing your thesis, please click here.
We are using OPNet to simulate our research networks. For details on the OPNet program, please click here.
For more information on Cartesian routing and Cartesian networks, contact Larry Hughes.
Last updated: 20 January 2004