Department: Electrical and Computer Engineering

Sponsoring Professor: Dr. Larry Hughes

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).

Our research considers alternatives to the unstructured mesh associated with the Internet, focussing on Cartesian networks, a two-dimensional 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 original Cartesian routing algorithm is for unicast transmissions in a Cartesian network, in which a packet's route is determined by the position of the router relative to that of the destination. The unicast routing algorithm 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 unicast routing.

Our research has progressed significantly since the original unicast design; for example, a loop-free broadcast algorithm has been designed. Current research includes the design of a congestion control mechanism for Cartesian networks, and considers different multicast algorithms for Cartesian networks.

About five MASc students are actively pursuing their graduate research using OPNET for simulation and visualization of their protocols. Other reseach projects using OPNET are under consideration.

Graduate Students:
Fisayo Adegoke - Congestion Control in Cartesian Networks
Subramaniam Ganesh - Fault Tolerance in Cartesian Networks
Zulfiqar Khan - OPNET support for Cartesian Networks
Shezhad Pradhan - Design and Implementation of a Collector Router
Shanthi Rao - Design and Implementation of an Arterial Router
Yasir Shah - Bluetooth Applications in OPNET
Haiyu Song - Multicast in Cartesian Networks

Further Information:
On Cartesian networks:
URL: www.dal.ca/~lhughes2/cartnet

Contact Larry Hughes at:
Telephone: 902.494.3950
E-mail: larry.hughes@dal.ca
URL: www.dal.ca/~lhughes2