perated networks. Each of these networks of networks (where a network is identified by a unique routing prefix or network ID, which is the part of the IP address that is the same for all network interfaces attached to the given IP network) actually forms an autonomous system. So, an AS is a collection of routers under the control of one authority (a company, telecom operator, etc.). These ASs are connected with each other through gateway routers to the Internet (i.e. to other ASs). Each AS is identified via a 16-bit or 32-bit AS number, where AS numbers are globally allocated and managed by IANA. With ASs as the basic architectural approach at present, we actually have two-tiers routing on the Internet [17]: Intra-AS routing. This is between routers belonging to a single AS (e.g. Routing Infor- mation Protocol (RIP), Open Shortest Path First (OSPF)). Inter-AS routing. This is routing between routers belonging to different ASs. Cur- rently, the globally accepted protocol for inter-AS routing is BGP-4 (Border Gateway Protocol version 4). So, while different routing protocols for routing inside a given AS can be used, the one used for routing between different ASs (inter-AS routing) is the same everywhere: BGP-4. BGP is in fact the "glue" that connects all autonomous parts of the global Internet network. How does BGP work? It is not a typical routing protocol which uses the shortest path routing principle, it is also based on policies that are influenced by business deci- sions about peering of the given network with other networks. BGP routers are typically implemented at the edge of the AS (toward the outside Internet network, from the AS's point of view), and they advertise (to other BGP routers with which they have an established BGP peering connection) reachability of other ASs or IP network prefixes through them. The Internet has become more global and interlinked over time, while at the same time dependence on the largest ISPs has decreased. The number of ASs continues to grow [21]. However, the average path 