Boolean routing on high degree chordal ring networks - Matroud Bashi, Atheer Abbas (2001)
Over the past twenty-five years, the telecommunication field has evolved rapidly. Telephone and computer networks, now nearly ubiquitous, provide access to voice, data and video services throughout the world. As networking technologies evolve and proliferate, researchers develop new traffic routing strategies. The problem of routing in a distributed system has been investigated and issues concerning Boolean routing schemes have been considered. All compact routing techniques minimise time and space complexity. A good routing algorithm optimises the time and space complexity and a routing algorithm that has O(1) time complexity and O(log n) space complexity for high degree chordal ring has been found. A Boolean Routing Scheme (BRS) has been applied on ring topology and regular chordal ring of degree three. It was found that the regular chordal ring of degree three can be represented geometrically. the regular chordal ring of degree three has been categorised into two categories; the first is the regular chordal ring of degree three that satisfies the following formula n mod 4 = 0 and the second other is n mod 4≠0, where n is the number of nodes that the graph contains. A BRS that requires O(log n) bits of storage at each node, O(1) time complexity to compute a shortest path to any destination for the regular chordal ring of degree three and Ө(log n) bits of storage at each node. O(1) time complexity to compute a shortest path to any destination for the ring topologies has been shown. The BRS has been applied on chordal ring of degree six. it has been found that the chordal ring of degree six can be represented geometrically and the representation would be in three dimensions (in the space). Very little is known about routing on high degree chordal rings. A BRS that requires O(log n) bits of storage at each node ,and 0(1) time complexity to compute a shortest path to any destination for the chordal ring of degree six topologyhas been shown. The chordal ring 0(27;9;3) has been considered as a case to apply BRS.