Ethernet Ring Dimensioning

A ring topology is a network configuration where the devices are connected to each other in a circular shape. Optical rings are widely used in mobile networks to transport the traffic from a base station to the backbone, through the mobile backhaul.

Definition of a ring

For the sake of simplicity, in this task, we define a ring as a connex graph which vertexes:

1. - have a degree 2 , which means they have 2 incident edges.
2. - are connected to two distinct vertexes

These two conditions ensure that there is a single link between each pair of adjacent nodes. Ring are represented as a string made of distinct characters, which position in the string reflects the position in the ring. For instance, the ring "AEFCBG" defines the following topology:

Shortest path asymmetric routing

Multiple traffic flows will be routed on the ring.
Each flow is routed on the shortest path from the ingress node (starting point of the traffic) to the egress node (exit point of the traffic).
If there are two shortest paths, the path which order fits the ring definition is kept .
Let's consider the following situation:

The path from A to B (and from B to A ) will be "A - G - B" , because it uses only two links, while the path going the other way around ("A - E - F - C - B") uses five links.
However, there are two paths of equal length to route a traffic from A to C : "A - E - F - C" and "A - G - B - C" . The first one, "A - E - F - C" , is kept: it is the same order as in the ring definition ( "AEFCBG" ).
The traffic from C to A will use the path "C - B - G - A" : the routing is asymmetric in that case.

Flow aggregation

A traffic flow is represented as a couple (s, dr) where:

1. - s is a string of length 2, containing the ingress node and the egress node .
2. - dr is the data rate in Gbps (gigabit per second).

The data rate of a traffic flow will be counted for all the links of the shortest path.
A traffic flow ("AB", 5) means that 5 Gbps will be routed on the shortest path from A to B .
We count 5 Gbps on the link "AG" and 5 Gbps on the link "GB" . For a traffic flow ("CA", 15) , we count 15 Gbps on the links "CB" , "BG" , and "GA" .
In order to simplify the model, we consider that the traffic flows ingress -> egress and egress -> ingress are equivalent with regard to dimensioning.
Two traffic flows ("AG", 3) and ("GA", 3) induce a 6-Gbps flow on the link AG , as would ("AG", 6) or ("GA", 6) : links are not directional . Given a list of traffic flows, we consider the resulting bandwidth on each link to dimension the ring.

There are five main types of Ethernet links used in mobile networks:

1. - Fast Ethernet (FE): 100 Mbps (or 0.1 Gbps)
2. - Gigabit Ethernet (GE): 1 Gbps.
3. - 10 Gigabit Ethernet (10GE): 10 Gbps
4. - 40 Gigabit Ethernet (40GE): 40 Gbps.
5. - 100 Gigabit Ethernet (100GE): 100 Gbps.

In order to select a type of link, we look for the smallest bandwidth allowing to carry the whole traffic with a single link . Handling a 5-Gbps traffic would require 50 FE links, 5 GE links, or 1 10GE link. Therefore, a 10GE Ethernet link is used. For a 15-Gbps traffic , a 40GE Ethernet link is required. For a traffic higher than 100 Gbps , 100GE Ethenet links are used (2 100GE Ethernet links for a 101-Gbps flow).

Given a ring and a list of traffic flows, you should return the number of Ethernet links of each type that are required to carry the resulting bandwidth:

In this example, we have 10 Gbps from E to C , 5 Gbps from A to C and 60 Gbps from A to B .
These traffic flows induce the following bandwidth: 15 Gbps from E to C , 5 Gbps from A to E and 60 Gbps from A to B .
The link dimensioning results in 2 100GE, 2 40GE and 1 10GE Ethernet links.

The result is given as a list containing the number of links for each category, from 100GE to FE. In our example, the result is [2, 2, 1, 0, 0]

Input: A variable number of arguments. The first one is a ring, represented as a string where each character is a node. The remaining arguments are traffic flows, represented as couples (s, dr) where s is a 2-characters string (ingress node, egress node) and dr is a positive value (traffic in Gbps).

Output: A list with 5 integers, one per type of link, in decreasing order of bandwidth capacity .

Example:

```checkio("AEFCBG", ("AC", 5), ("EC", 10), ("AB", 60)) == [2, 2, 1, 0, 0]
checkio("ABCDEFGH", ("AD", 4)) == [0, 0, 3, 0, 0]
checkio("ABCDEFGH", ("AD", 4), ("EA", 41)) == [4, 0, 3, 0, 0]```

How it is used: Links dimensioning is used for network planning and design. For real networks, various softwares are used to dimension the network based on the expected traffic load (for pre-sales engineers, when the network does not yet exist), or traffic measurements (for post-sales engineers to compute how much traffic the network can handle, and plan the network evolution).
However, real-life network dimensioning is much more complex than what is described in this task, as it deals with traffic differentiation and protection against equipment failure.

Preconditions:
The ring is a valid ring (connex, 2-degree nodes).
The traffic is a positive value (integer or float).

20
Settings
Code:
Other:
Invalid hot key. Each hot key should be unique and valid
Hot keys:
•  to Run Code: to Check Solution: to Stop:
CheckiO Extensions

CheckiO Extensions allow you to use local files to solve missions. More info in a blog post.

In order to install CheckiO client you'll need installed Python (version at least 3.8)

Install CheckiO Client first:

`pip3 install checkio_client`

`checkio --domain=py config --key=`

Sync solutions into your local folder

`checkio sync`

(in beta testing) Launch local server so your browser can use it and sync solution between local file end extension on the fly. (doesn't work for safari)

`checkio serv -d`

Alternatevly, you can install Chrome extension or FF addon

`checkio install-plugin`
`checkio install-plugin --ff`
`checkio install-plugin --chromium`

Read more here about other functionality that the checkio client provides. Feel free to submit an issue in case of any difficulties.

Pair Programming (Beta-version)

Welcome to Pair Programming! Engage in real-time collaboration on coding projects by starting a session and sharing the provided unique URL with friends or colleagues. This feature is perfect for joint project development, debugging, or learning new skills together. Simply click 'Start Session' to begin your collaborative coding journey!

Waiting for Pair Programming to start...

You are trying to join a pair programming session that has not started yet.

Please wait for the session creator to join.

Waiting for Pair Programming to reconnect...

It looks like the creator of the pair programming session closed the editor window.

It might happen accidentally, so that you can wait for reconnection.