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:
- - have a degree 2, which means they have 2 incident edges.
- - 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.
A traffic flow is represented as a couple (s, dr) where:
- - s is a string of length 2, containing the ingress node and the egress node.
- - 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.
Ethernet links dimensioning
There are five main types of Ethernet links used in mobile networks:
- - Fast Ethernet (FE): 100 Mbps (or 0.1 Gbps)
- - Gigabit Ethernet (GE): 1 Gbps.
- - 10 Gigabit Ethernet (10GE): 10 Gbps
- - 40 Gigabit Ethernet (40GE): 40 Gbps.
- - 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