A Caltech Library Service

Generalized Network Routing Metrics and Algorithms


Soedarmadji, Edwin (2008) Generalized Network Routing Metrics and Algorithms. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z94B2ZJD.


In this thesis, we introduce generalized network routing metrics that represent probability density parameters of the most popular communication channel models such as (a) the q-ary Symmetric Channel (q-SC) (b) the q-ary Erasure Channel (q-EC); (c) the Gilbert-Elliot Channel (GEC); and (d) the constrained Additive White Gaussian Noise (AWGN). The GEC is a very important for modelling correlated errors in channels such as the ubiquitous TCP/IP links and the wireless fading channels. In this thesis, we prove that channel models (a)--(d) can be used as inputs to the Generalized Dijkstra's Algorithm without resulting in any routing loop.

We also define our own generalized Dijkstra's algorithm that can solve a modified standard shortest path problem that features: (1) a subset of network nodes that are capable of reducing the accumulated path cost down to zero, and (2) a constraint that the cumulative cost of any feasible path must never exceed a prespecified maximum value. We call this modified problem the Gas Station Problem, and its solution the Gas Station Algorithm. The algorithm can be applied in many different areas such as: vehicle routing, project management, and most importantly, network communication.

We investigate various auxilliary synchronization algorithms used in popular routing protocols. Synchronization is used by routers to ensure that all routers operate on an identical routing table --- not a trivial task, considering network unreliabilities and possible malicious attacks. Our analysis produces a list of assumptions that guarantees synchronization. We also obtain the upper bounds to quantities such as transmission period, memory requirement, etc. In turn, these bounds can be used to rate network performance.

Finally, in a related contribution, we analyze message synchronization where a message is retransmitted only if the number of identical messages received exceeds a certain threshold. We define the Chinese Generals Problem as the problem of identifying the set of assumptions under which synchronization is guaranteed. This threshold-base message passing algorithm has the benefits of a tunable gain and a higher noise resistance.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Dijkstra's Algorithm; generalized network routing; network routing metrics
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Minor Option:Biology
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • McEliece, Robert J.
Thesis Committee:
  • McEliece, Robert J. (chair)
  • Hassibi, Babak
  • Bruck, Jehoshua
  • Low, Steven H.
  • Ho, Tracey C.
Defense Date:7 May 2008
Record Number:CaltechETD:etd-05302008-002429
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2313
Deposited By: Imported from ETD-db
Deposited On:04 Jun 2008
Last Modified:07 Jun 2023 17:34

Thesis Files

PDF (thesis_double.pdf) - Final Version
See Usage Policy.

PDF (thesis_single.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page