Boolean routing on high degree chordal ring networks
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 routi...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English English |
| Published: |
2001
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/8671/1/FSKTM_2001_12%20IR.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|