The Internet may be partitioned into independent Autonomous Systems (AS), typically containing a collection of routers under common administration. Routers within the same AS run the same routing algorithm [4]. Routing in the Internet can be divided into internal, or inside an AS, and external, or among ASes. The commonly used protocol for exchanging external AS routing information is the Border Gateway Protocol (BGP). BGP is a path-vector protocol that operates at the level of address blocks, or AS prefixes. Each AS prefix consists of a 32-bit address and a mask length, e.g., 192.0.2.0/24 consists of addresses from 192.0.2.0 to 192.0.2.255.
An AS-PATH is a sequence of intermediate ASes between source and destination routers that form a directed route for packets to travel. Neighboring ASes use BGP to exchange update messages about how to reach different AS prefixes. After each router makes a new local decision on the best route to a destination, it will send that route, or path information, along with accompanying distance metrics and path attributes, to each of its peers. As this information travels through the network, each router along the path prepends its unique AS number to a list of ASes in the BGP message. This list is the route's AS-PATH. An AS-PATH in conjunction with an AS prefix provides a specific handle for a one-way transit route through the network.