Back to search

University of Waterloo

An Optimization Problem of Internet Routing

Abstract

dc:description.abstract

As the Internet usage grows, existing network infrastructure must deal with increasing demand. One way to deal with this is to increase network capacity, and another, is to set network parameters appropriately. In this dissertation we contribute to the latter approach by determining the unique network paths data must flow over from its origin to its destination, while accounting for an Active Queue Management method, Random Early Detection (RED). We formulate a mixed integer non-linear program to determine the data paths, referred to as a routing policy. We prove that determining an optimal routing policy that accounts for RED is NP-Hard. Furthermore, in order for the generated routing policies to be real-world implementable, also known as realizable, we must determine weights for all arcs in the network such that solving the all pairs shortest path problem using these weights reproduces the routing policies. We show that determining if our generated routing policies are realizable is NP-Hard. Fortunately, using traffic data from three real-world networks, we are able to find realizable routing policies for these networks that account for RED, using an off-the-shelf solver, and policies found perform better than those used in those networks at the time the data was collected.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Liu, Jiaxin

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/8848

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Liu, Jiaxin. An Optimization Problem of Internet Routing. University of Waterloo, 2014. http://hdl.handle.net/10012/8848