Mikkel Thorup

Mikkel Thorup

Auto-generated profile, based on publicly available information

Mikkel Thorup

University of Copenhagen, Copenhagen, Denmark

Research Focus & Metrics

Academic Career Length

37Years (1990-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
7 November 2002
Verified
Conference Paper
Closed access
BFB. Fortz
B. Fortz
MTM. Thorup
M. Thorup
Open Shortest Path First (OSPF) is the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network opera- tor. The weights could be set proportional to their physical distances, but often the main goal is to avoid congestion, i.e. overloading of links, and a standard heuristic is to make the weight of a link inversely proportional to its capacity. Our starting point was a proposed AT&T WorldNet back- bone with demands projected from previous measurements. The desire was to optimize the weight setting based on the projected demands. We showed that optimizing the weight settings for a given set of demands is NP-hard, so we resorted to a local search heuristic. Surprisingly it turned out that for the proposed AT&T WorldNet backbone, we found weight settings that performed within a few percent from that of the optimal general routingwhere the flow for each demand is optimally distributed over all paths between source and des- tination. This contrasts the common belief that OSPF rout- ing leads to congestion and it shows that for the network and demand matrix studied we cannot get a substantially better load balancing by switching to the proposed more flexible Multi-protocol Label Switching (MPLS) technologies. Our techniques were also tested on synthetic internet- works, based on a model of Zegura et al. (INFOCOM'96), for which we did not always get quite as close to the opti- mal general routing. However, we compared with standard heuristics, such as weights inversely proportional to the ca- pacity or proportional to the physical distances, and found that, for the same network and capacities, we could support a 40%-150% increase in the demands. Our assumed demand matrix can also be seen as mod- eling service level agreements (SLAs) with customers, with demands representing guarantees of throughput for virtual leased lines.

1 January 2005 in Journal of the ACM
Verified
Journal Article
Open access
MTMikkel Thorup
Mikkel Thorup
UZUri Zwick
Uri Zwick
Let G = (V,E) be an undirected weighted graph with | V | = n and | E | = m . Let k ≥ 1 be an integer. We show that G = (V,E) can be preprocessed in O ( kmn 1/ k ) expected time, constructing a data structure of size O ( kn 1+1/ k ), such that any subsequent distance query can be answered, approximately, in O(k) time. The approximate distance returned is of stretch at most 2k −1, that is, the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k −1. A 1963 girth conjecture of Erdós, implies that Ω( n 1+1/ k ) space is needed in the worst case for any real stretch strictly smaller than 2 k +1. The space requirement of our algorithm is, therefore, essentially optimal. The most impressive feature of our data structure is its constant query time, hence the name "oracle". Previously, data structures that used only O ( n 1+1/ k ) space had a query time of Ω( n 1/ k ).Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs.

1 July 2001 in Journal of the ACM
Verified
Journal Article
Open access
JHJacob Holm
Jacob Holm
KLKristian de Lichtenberg
Kristian de Lichtenberg
MTMikkel Thorup
Mikkel Thorup
Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation costs are O (log 2 n ) for connectivity, O (log 4 n ) for minimum spanning forest, 2-edge connectivity, and O (log 5 n ) biconnectivity.

7 August 2002 in IEEE Journal on Selected Areas in Communications
Verified
Journal Article
Closed access
BFB. Fortz
B. Fortz
MTM. Thorup
M. Thorup
A system of techniques is presented for optimizing open shortest path first (OSPF) or intermediate system-intermediate system (IS-IS) weights for intradomain routing in a changing world, the goal being to avoid overloaded links. We address predicted periodic changes in traffic as well as problems arising from link failures and emerging hot spots.

1 May 1999 in Journal of the ACM
Verified
Journal Article
Open access
MTMikkel Thorup
Mikkel Thorup
The single-source shortest paths problem (SSSP) is one of the classic problems in algorithmic graph theory: given a positively weighted graph G with a source vertex s , find the shortest path from s to all other vertices in the graph. Since 1959, all theoretical developments in SSSP for general directed and undirected graphs have been based on Dijkstra's algorithm, visiting the vertices in order of increasing distance from s . Thus, any implementation of Dijkstra's algorithm sorts the vertices according to their distances from s . However, we do not know how to sort in linear time. Here, a deterministic linear time and linear space algorithm is presented for the undirected single source shortest paths problem with positive integer weights. The algorithm avoids the sorting bottleneck by building a hierarchical bucketing structure, identifying vertex pairs that may be visited in any order.

10 December 2002 in IEEE Communications Magazine
Verified
Journal Article
Closed access
BFB. Fortz
B. Fortz
JRJ. Rexford
J. Rexford
MTM. Thorup
M. Thorup
Traffic engineering involves adapting the routing of traffic to network conditions, with the joint goals of good user performance and efficient use of network resources. We describe an approach to intradomain traffic engineering that works within the existing deployed base of interior gateway protocols, such as Open Shortest Path First and Intermediate System-Intermediate System. We explain how to adapt the configuration of link weights, based on a networkwide view of the traffic and topology within a domain. In addition, we summarize the results of several studies of techniques for optimizing OSPF/IS-IS weights to the prevailing traffic. The article argues that traditional shortest path routing protocols are surprisingly effective for engineering the flow of traffic in large IP networks.