We present our work on the dimensioning of a packet-switching wavelength division multiplexing ring in order to reduce its infrastructure (capital expenditure) cost. We study a new all-optical architecture: the packed optical add-drop multiplexer (POADM). We aim to minimize the overall cost of the network by reducing the number of indispensable devices in the nodes and the number of required wavelengths. We formalize the packing problems underlying the ring dimensioning. The elements to be packed are made up of transmissions that share the same destination. We assume that elements can be cut before being packed into boxes. We furnish a complete theoretical analysis of the complexity and approximability of these problems. We define also several measures of quality for a cut and provide an optimal cutting strategy, according to these measures. Our subsequent contribution is a heuristic solution that solves the bi-criteria packing problem (the number of boxes and the number of cuts are minimized simultaneously). The exhaustive numerical results of this heuristic algorithm come next. We rely on our optimal cutting strategy to appraise the efficiency of other strategies. We also adapt the only existing POADM dimensioning algorithm, more restrictive than ours, and we confront it with our solution. The analysis of results allows us to provide network design guidelines to perform the dimensioning in the most efficient way.

Independent operator networks are called either Autonomous Systems (AS) or domains. Numerous studies based on complex measurement platforms have been carried out for over ten years now in order to discover the Internet topology on domain level. The routing realized by Border Gateway Protocol (BGP) is strongly influenced by commercial relationships which exist between domains, because domain operators do not want to make public the routes they know, as announcing certain routes would deprive them of a possible financial benefit. Consequently, routes available in BGP tables are valley-free and they are “spanned” on the inter-domain hierarchy. This property of BGP routes has an impact on the performance of protocols which are proposed to assure the QoS. We examined the existing Internet topologies gathered on the domain level over the six year period in the context of their hierarchy. We used aSHIIP, our random hierarchical topology generator, to induct the hierarchy into the collected topologies. We proposed new methods for detecting the core of a network. Thanks to this analysis we have been able to put forward solid inter-domain hierarchy induction methods which are implemented in our publicly available tool.

Numerous studies based on complex measurement platforms have been carried out for over ten years now in order to discover the Internet topology on domain level. It turns out that this topology exhibits certain invariant properties such as a distribution of node degree. This distribution follows a power law. Moreover, the revealed topology is hierarchical. The hierarchy is caused by commercial contracts signed between domain operators. The routing realized by Border Gateway Protocol (BGP) is strongly influenced by these commercial relationships because operators do not want to make public the routes they know, as announcing certain routes would deprive them of a possible financial benefit. Consequently, routes available in BGP tables are of particular shape (valley-free). This fact has an impact on the performance of protocols which are proposed notably to assure the Quality of Service (QoS). In order to evaluate the performance of new protocols in the inter-domain context their designers have to have at their disposal a random topology generator which is able to furnish a random graph whose nodes' degree follows a power law typical for the Internet, and to impose the commercial hierarchy on it. Our aSHIIP (autonomous Supélec Hierarchy Inter-domain Program) does both: its synthetic topologies are realistic and the hierarchy, which it introduces, corresponds to the one of the Internet. After explaining the reasons for our study, we present the methods which we propose to use for the flat Internet topology generation which satisfies the realism of the Internet. Next, we explain our algorithm used to induct the commercial hierarchy. The algorithm is heuristic because, as we prove in this paper, the underlying problem is NP-complete. We then evaluate the topologies generated with aSHIIP. The result is a reliable flat Internet-like topology generator which also allows the modeler to introduce the realistic hierarchy. We are convinced we can recommend it to modelers dealing with performance evaluation of protocols for the Internet on domain level.

Numerous studies based on complex measurement platforms have been carried out for over ten years now in order to discover the Internet topology on domain level. It turns out that this topology exhibits certain invariant properties such as a distribution of node degree. This distribution follows a power law. Moreover, the revealed topology is hierarchical. The hierarchy is caused by commercial contracts signed between domain operators. The routing realized by BGP is influenced by these relationships because operators do not want to make public the routes they know, as announcing certain routes would deprive them of a possible financial benefit. Consequently, routes available in BGP tables are valley-free. This fact has an impact on the performance of protocols which are proposed notably to assure the QoS. In order to evaluate the performance of new protocols in the inter-domain context their designers have to have at their disposal a random topology generator which is able to furnish a random graph whose nodes' degree follows a power law typical for the Internet, and to impose the commercial hierarchy on it. Our a SHIIP (autonomous Supelec Hierarchy Inter-domain Program) does both. It is a reliable flat Internet-like topology generator which also allows the modeler to introduce the realistic hierarchy.