| Reference - Hierarchically-organized-multihop-mobile-wireless-networks-quality-service-support
|
Check the attached document
- Address wireless networks QoS
- Link layer and network layer algorithms
- Distributed - Real Time applications
- Low cost
- Rapidly Deployable
- Self organizing
- No prior infrastructure ( Adhoc networking)
(i) Location Manager : Movement of nodes within the clusters
(ii) Adaptive Link Control : Perceived and desired link quality metrics
(iii) QoS manager: mean value and Expected values of cluster's quality
- Parent ->child clusters (link state information distributed by QoS manager)
- n clusters: n-1 children get link state packets from this manager
(iv) Multicast Manager: controls access to multicast groups and sessions extant within cluster and that quickly joins endpoints
- Routing information dissemination: Link state packets
- Connectivity information
- Service information pertaining to clusters and virtual gateways
- Compute one or more feasible routes for a "session"
- based on link-state information received from other clusters
- Current location of the end point with respect to hierarchical structure
- Service requirements
Nodes ---> Routers ---> clusters ----> super clusters
- Peer border routers
- Virtual gateways: connect two adjacent clusters
- Virtual link (between two virtual gateways)
Aggregation of one or more peer border router pairs: two border routers from different clusters
- Role of router in a cluster
- Border router : Router that has one neighbor that does not belong to same cluster
- Interior router : Router that has no neighbors in different clusters ( opposite f border router)
- Node :
- source/destination of packets
- Node ------> Registers with router ( based on some link parameters)
- Moves out of the reach of router >> it is affiliated with : Register with another router
- Router -------> cell head ( serves more than 1 cell/ nodes)
- Many nodes affiliate with this router and router becomes cell head for these
- routers come together ----> Clusters
*Cluster ----> contains only group of routers (at lowest level)
- contains one/ more clusters as well : super cluster
- Every cluster has only one parent
- Every router belongs to exactly one cluster
- formed based on connectivity
- Number of endpoints limited (prevent traffic concentration)
- Node has link quality vector ( based on which it decides which router to associate with )
- Bound on Size of clusters fixed --> better control and routing
- Limited number of hierarchical levels ---> prevent too many sub-optimal routes ; maintenance overhead
- Virtual gateways must be stable -->inter cluster connection stability (change in link state distribution overhead increases
| Identifying network Elements
|
- Addresses are autonomously acquired and may change with time
- Every router and end point assumed to have globally unique identity ( lets say GUID)
- router ID
- Cluster ID -- sequence of router ID's indicating the hierarchical relation among clusters
level 0 cluster Address => router ID
- Node Affiliation with router : << Affiliation protocol>>
- End point activated
- Build link vector
- selection of router
- Node :Affiliation request -------> Router
- Router: Response ------------>Node (only if it can accommodate )
- Handshake with each of the routers in decreasing order of preference
- Link quality gets low : node restarts affiliation procedure
| node may not be affiliated to "best " (i.e.,closest) router but the one whose link quality that may be acceptable
|
- Link state topology information :
- Link state data collected during routing: used for clustering as well
| << unlike other Distributed algorithms : Quick convergence of clustering algorithm
|
| unlike Centralized algorithms : Avoids single point of failure >>
|
- Router movement
- Router birth
- Router death
| cluster birth /cluster death / cluster membership change /division of cluster (cluster split)
|
- Number of routers in clusters are above acceptable threshold: requires split (checked by leader/backup)
- must maintain connectivity between routers in resulting clusters
- Equalize cluster sizes
- Routers in a cluster are “ranked” in order of their router Ids (independent of the link state info)
- Lowest id router assumes leadership (Cluster Leader)
- Splitting / Merging performed by leader who sends related info to appropriate nodes (subnet of routers) to begin merge/split
- Run splitting heuristic on link state database: partition into two disjoint clusters
- broadcast info about new cluster membership
- Virtual gateway membership to every router in cluster
- Each router that gets this info updates its cluster related state appropriately
*Virtual gateways are automatically born as a result of split
- Uses Graph Algorithm:
- Splits a given graph (of cluster) : S1 and S2
- If number is less than threshold : leader checks this (Router)
- find most appropriate neighboring cluster: using the data on the cluster size available because of link state packet updates
- Sum of the size of cluster 1+ cluster 2 < cluster size split threshold (but as close as possible to preferred size: to attain equal size pattern)
- If such cluster (candidate for merge) is found: Perform merge and inform all routers involved about the change
| Virtual Gateway: create/destroy/grow/split/merge /shrink
|
- Create / Destroy: like above
- Distributed protocol involving handshake between routers involved in change
- Periodically each router checks if it has to initiate such a procedure (how frequent indicates the sensitivity to change in network)
- switch id
- Role (border/interior)
- Virtual gateway ID (if applicable) information carried of router sees a neighbor router (adjacent) and can form virtual gateway -
- Router with lower id initiates handshake to form VG
- Handshake includes selection of VG id
