{"id":{"repo_id":"aachen","oai_identifier":"oai:publications.rwth-aachen.de:52748"},"canonical_url":"https://search.dev.ndltd.org/etd/aachen/oai:publications.rwth-aachen.de:52748","repository":{"repo_id":"aachen","name":"RWTH Aachen University","base_url":"https://publications.rwth-aachen.de/oai2d"},"display":{"title":"Dynamic selfish routing","abstract":"This thesis deals with dynamic, load-adaptive rerouting policies in game theoretic settings. In the Wardrop model, which forms the basis of our dynamic population model, each of an infinite number of agents injects an infinitesimal amount of flow into a network, which in turn induces latency on the edges. Each agent may choose from a set of paths and strives to minimise its sustained latency selfishly. Population states which are stable in that no agent can improve its latency by switching to another path are referred to as Wardrop equilibria. A variety of results in this model have been obtained recently. Most of these revolve around the \"price of anarchy\", which measures the degradation of performance due to the selfish behaviour of the agents as compared to a centrally optimised solution. Most of these analyses consider the notion of Wardrop equilibria as a solution concept of selfish routing games, but disregard the question of how such an equilibrium can be attained in the first place. In fact, common game theoretic assumptions needed for the motivation of equilibria in general strategic games are not satisfied for routing games in large networks, the Internet being the prime example. These assumptions comprise accurate knowledge of the network and its latency functions as well as unbounded rationality and reasoning capabilities. The question of how Wardrop equilibria can be attained by a population of selfish agents is the central topic of this thesis. Our first approach is inspired by evolutionary game theory. We show that Wardrop equilibria actually satisfy a stronger stability criterion, called evolutionary stability, which can be motivated by milder assumptions. We model a population of agents following some very simple randomised selfish rules allowing them to exchange their path for a better one from time to time. An agent samples another path according to some probability distribution and possibly exchanges its current path for the new one with a probability that increases with the latency gain. The behaviour of such a population over time can be described in terms of a system of differential equations. For a concrete choice of probability distributions involved in the above rules, these differential equations take the form of the so-called replicator dynamics. As a first result, we show that a population following this dynamics converges towards the set of Wardrop equilibria. This convergence result implicitly assumes perfect information in that rerouting decisions made by other agents are observable by other agents immediately. In communication networks, however, such rerouting decisions may be observed only with a delay. In both theory and practise, it is known that rerouting decisions based on stale information may lead to undesirable oscillation effects which seriously harm performance. We consider an extension of our dynamic population model in which information is updated only at intervals of a given length. We show that, despite of this, convergence to Wardrop equilibria is still possible. For any class of latency functions with bounded slope and any finite update period length, policies from a large class converge towards Wardrop equilibria provided that they satisfy a certain smoothness condition. This condition requires the migration rate to be reduced by a factor that is reciprocal to the maximum slope and the update period length. Finally, we show that Wardrop equilibria can be approached quickly. This is an issue of particular importance if the network or the flow demands themselves may change over time. To measure the speed of convergence, we consider the time to reach approximate Wardrop equilibria. We show that by applying a clever sampling technique it is possible to reach an approximate Wardrop equilibrium in time polynomial in the approximation quality and the representation length of the network. In particular, our bounds depend on the maximum slope of the latency functions only logarithmically, which improves over earlier results in similar models which depend linearly on this parameter. We show that the crucial parameter that limits the speed of convergence is not the slope, but rather the elasticity of the latency functions. Based on these positive theoretical results, we design a dynamic traffic engineering protocol which we evaluate by simulations. Our protocol splits traffic bound for the same destination among alternative next-hop routers and continuously adjusts the splitting ratios. The simulation framework involves significantly more details than the Wardrop model does. For example, our simulations feature a full TCP implementation at packet level and include realistic HTTP workload generated on the basis of realistic statistical properties of Web users. The simulation results are in good correspondence with theory. We see that our protocol in fact converges quickly and significantly improves the throughput of an autonomous system.","abstract_html":"This thesis deals with dynamic, load-adaptive rerouting policies in game theoretic settings. In the Wardrop model, which forms the basis of our dynamic population model, each of an infinite number of agents injects an infinitesimal amount of flow into a network, which in turn induces latency on the edges. Each agent may choose from a set of paths and strives to minimise its sustained latency selfishly. Population states which are stable in that no agent can improve its latency by switching to another path are referred to as Wardrop equilibria. A variety of results in this model have been obtained recently. Most of these revolve around the "price of anarchy", which measures the degradation of performance due to the selfish behaviour of the agents as compared to a centrally optimised solution. Most of these analyses consider the notion of Wardrop equilibria as a solution concept of selfish routing games, but disregard the question of how such an equilibrium can be attained in the first place. In fact, common game theoretic assumptions needed for the motivation of equilibria in general strategic games are not satisfied for routing games in large networks, the Internet being the prime example. These assumptions comprise accurate knowledge of the network and its latency functions as well as unbounded rationality and reasoning capabilities. The question of how Wardrop equilibria can be attained by a population of selfish agents is the central topic of this thesis. Our first approach is inspired by evolutionary game theory. We show that Wardrop equilibria actually satisfy a stronger stability criterion, called evolutionary stability, which can be motivated by milder assumptions. We model a population of agents following some very simple randomised selfish rules allowing them to exchange their path for a better one from time to time. An agent samples another path according to some probability distribution and possibly exchanges its current path for the new one with a probability that increases with the latency gain. The behaviour of such a population over time can be described in terms of a system of differential equations. For a concrete choice of probability distributions involved in the above rules, these differential equations take the form of the so-called replicator dynamics. As a first result, we show that a population following this dynamics converges towards the set of Wardrop equilibria. This convergence result implicitly assumes perfect information in that rerouting decisions made by other agents are observable by other agents immediately. In communication networks, however, such rerouting decisions may be observed only with a delay. In both theory and practise, it is known that rerouting decisions based on stale information may lead to undesirable oscillation effects which seriously harm performance. We consider an extension of our dynamic population model in which information is updated only at intervals of a given length. We show that, despite of this, convergence to Wardrop equilibria is still possible. For any class of latency functions with bounded slope and any finite update period length, policies from a large class converge towards Wardrop equilibria provided that they satisfy a certain smoothness condition. This condition requires the migration rate to be reduced by a factor that is reciprocal to the maximum slope and the update period length. Finally, we show that Wardrop equilibria can be approached quickly. This is an issue of particular importance if the network or the flow demands themselves may change over time. To measure the speed of convergence, we consider the time to reach approximate Wardrop equilibria. We show that by applying a clever sampling technique it is possible to reach an approximate Wardrop equilibrium in time polynomial in the approximation quality and the representation length of the network. In particular, our bounds depend on the maximum slope of the latency functions only logarithmically, which improves over earlier results in similar models which depend linearly on this parameter. We show that the crucial parameter that limits the speed of convergence is not the slope, but rather the elasticity of the latency functions. Based on these positive theoretical results, we design a dynamic traffic engineering protocol which we evaluate by simulations. Our protocol splits traffic bound for the same destination among alternative next-hop routers and continuously adjusts the splitting ratios. The simulation framework involves significantly more details than the Wardrop model does. For example, our simulations feature a full TCP implementation at packet level and include realistic HTTP workload generated on the basis of realistic statistical properties of Web users. The simulation results are in good correspondence with theory. We see that our protocol in fact converges quickly and significantly improves the throughput of an autonomous system.","abstract_has_math":false,"creators":["Fischer, Simon"],"institution":"Publikationsserver der RWTH Aachen University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Vöcking, Berthold"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2007,"date_issued":"2007","date_published":"2007","updated_at":"2026-07-30T19:41:00Z","subjects":["info:eu-repo/classification/ddc/004","Spieltheorie","Evolutionäre Spieltheorie","Eigennütziges Routing","Informatik","Wardrop Gleichgewicht","Konvergenzzeit","Adaptive Protokolle","Wardrop equilibrium","convergence time","adaptive protocols"],"languages":["eng"],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114948%22"],"render_values":[{"text":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114948%22","href":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114948%22","code":true}]}]},"links":{"outbound_url":"https://publications.rwth-aachen.de/record/52748","outbound_label":"Repository record","outbound_source":"dc:identifier"},"source_record":{"url":"https://publications.rwth-aachen.de/oai2d?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Apublications.rwth-aachen.de%3A52748","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Vöcking, Berthold"]},{"key":"dc:creator","label":"Author","values":["Fischer, Simon"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:coverage","label":"Dc Coverage","values":["DE"]},{"key":"dc:date","label":"Dc Date","values":["2007"]},{"key":"dc:publisher","label":"Institution","values":["Publikationsserver der RWTH Aachen University"]},{"key":"dc:relation","label":"Dc Relation","values":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-19396"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["info:eu-repo/classification/ddc/004","Spieltheorie","Evolutionäre Spieltheorie","Eigennütziges Routing","Informatik","Wardrop Gleichgewicht","Konvergenzzeit","Adaptive Protokolle","Wardrop equilibrium","convergence time","adaptive protocols"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/record/52748","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114948%22"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis deals with dynamic, load-adaptive rerouting policies in game theoretic settings. In the Wardrop model, which forms the basis of our dynamic population model, each of an infinite number of agents injects an infinitesimal amount of flow into a network, which in turn induces latency on the edges. Each agent may choose from a set of paths and strives to minimise its sustained latency selfishly. Population states which are stable in that no agent can improve its latency by switching to another path are referred to as Wardrop equilibria. A variety of results in this model have been obtained recently. Most of these revolve around the \"price of anarchy\", which measures the degradation of performance due to the selfish behaviour of the agents as compared to a centrally optimised solution. Most of these analyses consider the notion of Wardrop equilibria as a solution concept of selfish routing games, but disregard the question of how such an equilibrium can be attained in the first place. In fact, common game theoretic assumptions needed for the motivation of equilibria in general strategic games are not satisfied for routing games in large networks, the Internet being the prime example. These assumptions comprise accurate knowledge of the network and its latency functions as well as unbounded rationality and reasoning capabilities. The question of how Wardrop equilibria can be attained by a population of selfish agents is the central topic of this thesis. Our first approach is inspired by evolutionary game theory. We show that Wardrop equilibria actually satisfy a stronger stability criterion, called evolutionary stability, which can be motivated by milder assumptions. We model a population of agents following some very simple randomised selfish rules allowing them to exchange their path for a better one from time to time. An agent samples another path according to some probability distribution and possibly exchanges its current path for the new one with a probability that increases with the latency gain. The behaviour of such a population over time can be described in terms of a system of differential equations. For a concrete choice of probability distributions involved in the above rules, these differential equations take the form of the so-called replicator dynamics. As a first result, we show that a population following this dynamics converges towards the set of Wardrop equilibria. This convergence result implicitly assumes perfect information in that rerouting decisions made by other agents are observable by other agents immediately. In communication networks, however, such rerouting decisions may be observed only with a delay. In both theory and practise, it is known that rerouting decisions based on stale information may lead to undesirable oscillation effects which seriously harm performance. We consider an extension of our dynamic population model in which information is updated only at intervals of a given length. We show that, despite of this, convergence to Wardrop equilibria is still possible. For any class of latency functions with bounded slope and any finite update period length, policies from a large class converge towards Wardrop equilibria provided that they satisfy a certain smoothness condition. This condition requires the migration rate to be reduced by a factor that is reciprocal to the maximum slope and the update period length. Finally, we show that Wardrop equilibria can be approached quickly. This is an issue of particular importance if the network or the flow demands themselves may change over time. To measure the speed of convergence, we consider the time to reach approximate Wardrop equilibria. We show that by applying a clever sampling technique it is possible to reach an approximate Wardrop equilibrium in time polynomial in the approximation quality and the representation length of the network. In particular, our bounds depend on the maximum slope of the latency functions only logarithmically, which improves over earlier results in similar models which depend linearly on this parameter. We show that the crucial parameter that limits the speed of convergence is not the slope, but rather the elasticity of the latency functions. Based on these positive theoretical results, we design a dynamic traffic engineering protocol which we evaluate by simulations. Our protocol splits traffic bound for the same destination among alternative next-hop routers and continuously adjusts the splitting ratios. The simulation framework involves significantly more details than the Wardrop model does. For example, our simulations feature a full TCP implementation at packet level and include realistic HTTP workload generated on the basis of realistic statistical properties of Web users. The simulation results are in good correspondence with theory. We see that our protocol in fact converges quickly and significantly improves the throughput of an autonomous system."]},{"key":"dc:source","label":"Dc Source","values":["Aachen : Publikationsserver der RWTH Aachen University XVI, 156 S. : Ill., graph. Darst. (2007). = Aachen, Techn. Hochsch., Diss., 2007"]},{"key":"dc:title","label":"Title","values":["Dynamic selfish routing"]}]}],"canonical_facts":{"dc:contributor":["Vöcking, Berthold"],"dc:coverage":["DE"],"dc:creator":["Fischer, Simon"],"dc:date":["2007"],"dc:description":["This thesis deals with dynamic, load-adaptive rerouting policies in game theoretic settings. In the Wardrop model, which forms the basis of our dynamic population model, each of an infinite number of agents injects an infinitesimal amount of flow into a network, which in turn induces latency on the edges. Each agent may choose from a set of paths and strives to minimise its sustained latency selfishly. Population states which are stable in that no agent can improve its latency by switching to another path are referred to as Wardrop equilibria. A variety of results in this model have been obtained recently. Most of these revolve around the \"price of anarchy\", which measures the degradation of performance due to the selfish behaviour of the agents as compared to a centrally optimised solution. Most of these analyses consider the notion of Wardrop equilibria as a solution concept of selfish routing games, but disregard the question of how such an equilibrium can be attained in the first place. In fact, common game theoretic assumptions needed for the motivation of equilibria in general strategic games are not satisfied for routing games in large networks, the Internet being the prime example. These assumptions comprise accurate knowledge of the network and its latency functions as well as unbounded rationality and reasoning capabilities. The question of how Wardrop equilibria can be attained by a population of selfish agents is the central topic of this thesis. Our first approach is inspired by evolutionary game theory. We show that Wardrop equilibria actually satisfy a stronger stability criterion, called evolutionary stability, which can be motivated by milder assumptions. We model a population of agents following some very simple randomised selfish rules allowing them to exchange their path for a better one from time to time. An agent samples another path according to some probability distribution and possibly exchanges its current path for the new one with a probability that increases with the latency gain. The behaviour of such a population over time can be described in terms of a system of differential equations. For a concrete choice of probability distributions involved in the above rules, these differential equations take the form of the so-called replicator dynamics. As a first result, we show that a population following this dynamics converges towards the set of Wardrop equilibria. This convergence result implicitly assumes perfect information in that rerouting decisions made by other agents are observable by other agents immediately. In communication networks, however, such rerouting decisions may be observed only with a delay. In both theory and practise, it is known that rerouting decisions based on stale information may lead to undesirable oscillation effects which seriously harm performance. We consider an extension of our dynamic population model in which information is updated only at intervals of a given length. We show that, despite of this, convergence to Wardrop equilibria is still possible. For any class of latency functions with bounded slope and any finite update period length, policies from a large class converge towards Wardrop equilibria provided that they satisfy a certain smoothness condition. This condition requires the migration rate to be reduced by a factor that is reciprocal to the maximum slope and the update period length. Finally, we show that Wardrop equilibria can be approached quickly. This is an issue of particular importance if the network or the flow demands themselves may change over time. To measure the speed of convergence, we consider the time to reach approximate Wardrop equilibria. We show that by applying a clever sampling technique it is possible to reach an approximate Wardrop equilibrium in time polynomial in the approximation quality and the representation length of the network. In particular, our bounds depend on the maximum slope of the latency functions only logarithmically, which improves over earlier results in similar models which depend linearly on this parameter. We show that the crucial parameter that limits the speed of convergence is not the slope, but rather the elasticity of the latency functions. Based on these positive theoretical results, we design a dynamic traffic engineering protocol which we evaluate by simulations. Our protocol splits traffic bound for the same destination among alternative next-hop routers and continuously adjusts the splitting ratios. The simulation framework involves significantly more details than the Wardrop model does. For example, our simulations feature a full TCP implementation at packet level and include realistic HTTP workload generated on the basis of realistic statistical properties of Web users. The simulation results are in good correspondence with theory. We see that our protocol in fact converges quickly and significantly improves the throughput of an autonomous system."],"dc:identifier":["https://publications.rwth-aachen.de/record/52748","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114948%22"],"dc:language":["eng"],"dc:publisher":["Publikationsserver der RWTH Aachen University"],"dc:relation":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-19396"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:source":["Aachen : Publikationsserver der RWTH Aachen University XVI, 156 S. : Ill., graph. Darst. (2007). = Aachen, Techn. Hochsch., Diss., 2007"],"dc:subject":["info:eu-repo/classification/ddc/004","Spieltheorie","Evolutionäre Spieltheorie","Eigennütziges Routing","Informatik","Wardrop Gleichgewicht","Konvergenzzeit","Adaptive Protokolle","Wardrop equilibrium","convergence time","adaptive protocols"],"dc:title":["Dynamic selfish routing"],"dc:type":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]},"updated_at":"2026-07-30T19:41:00Z"}