Loading...
Please wait, while we are loading the content...
Similar Documents
Delay bounded and load balanced oblivious routing algorithms
| Content Provider | Semantic Scholar |
|---|---|
| Author | Singh, Arjun Kilani, Mohamed Papadopoulos, Dimitris Goyal, Kiran B. |
| Copyright Year | 2001 |
| Abstract | Routing algorithms in fixed topologies (like meshes and torii) may be oblivious or adaptive in nature. Adaptive algorithms make routing decisions while taking the network’s state of congestion into account. However, they cause a lot of overhead in the complexity of implementation as well as in the congestion of the network (due to control packets). On the other hand, oblivious algorithms ignore network congestion while taking routing decisions basing them purely on the source and the destination of each packet. Hence, they are easier to implement and their analysis is also more tractable than that of adaptive algorithms. In our project we concentrate on latency and load balance that oblivious routing algorithms can offer under any traffic pattern. We first try to come up with a suitable algorithm that achieves the best tradeoff between latency and load balance under adversarial traffic. We then simulate them using a simulator written in C. Finally, we attempt to come up with analytical bounds for the delays in some of the routing algorithms. We discuss and compare the threoretical curves with the simulated plots. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.iis.ee.ethz.ch/~fdimitri/Delay%20Bounded%20and%20load%20balanced%20%20oblivious%20routing%20algorithmes.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
